Constant-time bounds on offline 2-choice hashing?
You're missing the (obvious but) unstated caveat of "with high probability", I think.  If you're hashing randomly, there's some chance all items choose the same two buckets.  With high probability, you can get constant load.  I think I recall this was first shown to me by Alan Frieze, but I can't recall the reference.  Cuckoo hashing provides another way of showing this is true.