XBee Packetization problem
Yes, the only reliable option I have found to avoid packets being split is to use the API mode. There is an Arduino library to help you with that already, xbee-arduino from Andrew Rapp. Don't forget to configure API mode escaped, otherwise the frames will be considered wrong, nothing will be received, and you'll not understand why. On the computer side, the xbee-api library (Java) from the same author is great for debugging.

I have set together a page with the XBee tips and resources I found most useful when I was doing something similar with an XBee.