SOLVED: Udev idling on startup
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!