Alright, it's time to nail this thing down. I think it is data rate and I just couldn't find that for the XBees (data overload from google).
So, I propose a test that should take a lot less time than you've wasted so far. Set the baudrates on both of them to 9600 and repeat PaulS's test. I bet it works. Then go to 57K, I bet it works for a while and then craps. And so forth.
edit: Spoke too soon, the datarate is 250Kbps for the low power 2.4GHz modules. That should be enough, but I still think the test would be useful.
Yet another edit: I just remembered the overhead. These thing build everything into a packet and send acks and so forth back and forth. You could well be exceeding the data rate. Working from memory, the packet is a bunch bigger than the data for small messages what with the various addresses, checksums, sequence numbers and so forth. They even do this in transparent mode, I mix my devices using one mode for this one and the other mode for that one. So, the test makes even more sense.