Setting udev's syslog level to DEBUG in /etc/udev/udev.conf helped me see what was the bottleneck. After the 30 seconds long pause, the next couple of message were about "settling", which, along with the graph that bootchart drawed for me and an afternoon of reading manpages led me to think that what was taking long was "udevadmin settle".
Indeed I was right. Cheking /etc/init.d/udev, near to the end there was a call to udevadmin settle. I added --timeout=1 to that line (default is 180, both in seconds), knowing that it wouldn't hurt, because I always hit Ctrl+C when the delay began anyway. And it worked! Finally I'm done. Thanks everyone who helped! André
