I have only ever seen the script upgrade phase take minutes, never hours, and I've done a few.

We have 'stagger patched' clusters as well, theoretically the two nodes could run at different patch levels indefinitely.

You would not be able to fail back to an unpatched node, which is why they are removed from the list of possible owners.

see this KB if you have not already

http://support.microsoft.com/kb/958734