Communicator Error ID:5001 "The following message was not delivered"

I have recently encountered this error in an OCS 2007 deployment with a mix of Communicator 2007 and Communicator 2005 clients. The problem was specifically that the Communicator 2005 client did not have the latest hotfix installed: (released December 19, 2008). The Communicator 2007 client had the latest hotfix, but not the Communicator 2005 client.

Another possibility [...]