How long to hold key combinations when booting a Mac?
In general, you should hold the key(s) down until they take effect. For single-user and verbose modes, that means hold them until you see text start to appear. For the others, it's generally ok to let go once you see the Apple in the middle of the screen (the Apple is drawn by the booter, which loads after the firmware has detected startup options).

If you have FileVault 2 (full volume encryption) set up, things are a little more complicated, since some key combinations (mainly single-user, verbose, and safe boot) don't take effect until after you've authenticated to unlock the startup volume. It currently seems to do a good job of detecting the key combos before the authentication screen, then having them take effect after you "log in". But if that's not working for you, try holding them down as you press return on the FV2 authentication screen, and keep holding them until you see them take effect.