Argh!! Max5 <-> XBee data is jamming

This is a nightmare. I'm in the last phase before a deadline and the installation I'm working on is having trouble with XBee. I have tried everything so I'm trying this as a last resort. Maybe someone can help me out at the last minute....

I'm sending messages from Max5 (using the serial object) to my XBee module (series 1 1mW). Occasional messages work fine, but as soon as I'm sending data at a higher rate from Max, the communication is jammed and messages are lost.

With USB connection everything works like it should.

Modules are connected at 115200 bps.

I'm using the Arduino Messenger library to communicate back and forth. I've tried to increase the Messenger buffer size in Messenger.h to 1024. It doesn't seem to make any difference.

What else can I try??