This one gave me headache: the Mollom module in Drupal 6 returned a 401: unauthorized. However: there was no firewall, no incorrect key, and I really got a response back from the server. Top of the bill: it worked on my dev-machine but not on the server.
Till I noticed the time of log reports didn’t match the real time. It was 17:15 while Drupal said 16:58. A time difference of almost 20 minutes. I set the time correct and ta-dah: Mollom works.