Flesso,
I have a client with all their domains registered with 1&1 (he has about 90), I have recently changed his name servers over to hosting at eUKHost and it took about 3 hours to propagate and using
www.dnsstuff.com I could see it updated all the primary NIC's in one go.
I did something similar with ukReg.com and it took about the same time but it updated the NIC's 1 by 1.
That was my experience anyway.