I made some progress on this after chatting live with Eric from Digi support, and also reading around HOWTOs on the net.
First point is that the XBee 2.5 model is discontinued and no longer supported by Digi, even though it's still pretty widely sold. Eric mentioned that there are some better and more up-to-date models available, I think the 'ZB' line rather than the 'ZNet' is what you want. But I'm not completely clear on that yet (and I have the 2.5 which I wanted to get working).
Next, because the XBee 2.5 and XBee PRO 2.5 are no longer supported, the firmware is not available automatically from the X-CTU program. To get the firmware, you can still download it manually, and then use the 'File' option in the X-CTU download tool to get X-CTU to use the latest firmware. The firmware I needed was on this page: http://www.digi.com/support/productdetl.jsp?pid=3261&osvid=0&s=269&tp=2&tp2=0
Next, you can follow the information in the 'Xbee Configuration guide', see link at http://www.arduino.cc/en/Guide/ArduinoXbeeShield
You have to set up one XBee as 'ZNET 2.5 COMMUNICATOR AT' (the 'home base' xbee) and the other as 'ZNET 2.5 ROUTER/ENDPOINT AT' (the 'remote' xbee). You can assign names (ID) and network IDs (PAN ID) to both XBees using X-CTU.
Using this approach, the serial test worked OK, so it's looking good. According to Eric, what one should really be doing here is upgrading the firmware to the new 'ZB' feature set, for which instructions are here:
http://ftp1.digi.com/support/documentation/upgradingfromznettozb.pdf
I'm entirely sure why one should do that, other than to enable digi to support you better, because they don't actually support the ZNet modules, which apparently date from year 2006.
Best Answer
The XBee serial interface implements an auto baud feature, which works on the first single character sent to it. So when you reset the module, it is ready to accept the character and synchronize with the baud you have set, but it cannot do so again after that.
Search for the term "auto baud" in any XBee user manual to learn more about this feature.