Thanks to Seif Attar for highlighting this problem.
It seems MSMQ doesn’t like sending to computers with names longer than 15 characters (which some may remember is the NetBIOS limitation).
To try it out, I created a queue on a Windows XP machine with a computer name of VeryLongMSMQServer and sent off some test messages to
DIRECT=os:verylongmsmqserver\private$\txqueue
I requested acknowledgements so I could see any errors and wasn’t disappointed:

As soon as I renamed the machine to ShortMSMQServer, restarted and sent new messages to
DIRECT=os:shortmsmqserver\private$\txqueue
the problem disappeared:

The messages are delivered to the destination’s queue manager in both cases but are rejected when the machine name is too long.
My suspicion is that this is a NetBIOS limitation. When I initially changed the machines computer name to one that was too long, Windows XP complained “The NetBIOS name of the computer is limited to 15 bytes. The NetBIOS name will be shortened to “VERYLONGMSMQSER”.:

I did try enabling the IgnoreOSNameValidation registry value in case that would help but no luck.