Some more details on the very rare Signature Verification Failed error:
From the logs shown, the provider [MyOpenId] has processed several logins from this one person within a very small duration (less than a second). Each authentication received has a nonce in it that can only be used once. As a "dumb-mode" RP, Stack Overflow sends each assertion to myopenid.com for verification, and myopenid.com will (or should) verify the first one, and reject the subsequent ones, if it's actually the same assertion used multiple times, which it likely is.
My only theory to explain what you're seeing is that this person (or his proxy?) is repeating his HTTP request that sends the assertion back to Stack Overflow. And his browser displays the response that came from one any of the tries besides the first one. I don't know why a proxy would do that, but according to the HTTP spec, a GET request is supposed to be entirely benign, which the OpenID spec violates, so I might believe a problem here. One other possible source of the problem would be a browser "accelerator" plugin that aggressively fetches HTTP resources, resulting possibly in multiple calls.
Verifying that this is the problem might be difficult. Certainly you can try using Fiddler on his computer to see if the assertion is sent to Stack Overflow more than once, but that won't capture any funny behavior at the proxy level.
So if you see this in your the OpenID provider logs..
148 ms ago 10.0.0.1 Approve for http://stackoverflow.com/users/authenticate/
269 ms ago 10.0.0.1 Approve for http://stackoverflow.com/users/authenticate/
0 min ago 0.0.0.1 Approve for http://stackoverflow.com/users/authenticate/
that's bad -- see the multiples, there? And in such a short timeframe?
It should look more like this, one login, one record:
119 ms ago 10.0.0.1 Approve for http://stackoverflow.com/users/authenticate/
316 ms ago 10.0.0.1 Sign in by password
Andrew (resident OpenID expert) noted that some OpenID providers do not validate the time nonces, so you wouldn't necessarily see a problem when using Google or Yahoo. That's why this one is somewhat specific to myopenid and rapid logins.