I realize this is probably not a plugin issue, but thought you might have suggestions. When I use Contact Form 7, I always receive the e-mail I'm supposed to get when someone uses the form. The problem is that about 50% of the time, the user gets a message that says "Failed to send your message" (even though the message was, in fact, sent properly). My guess is it isn't getting a return response from the server fast enough on occasion. The smtp server for our organization is not on the same server as the WordPress install.
Not sure whether to expect an answer, but thought I'd ask. I use Ubuntu as the webserver.