Seeing the same thing of late w/ 9.0.0.1 for a user regardless of which device he uses....iPhone/iPad (ActiveSync) or Android (native client). All show the same behavior as the OP.
Although I am using an HA setup w/ MS SQL backend, there's only one box running Traveler connected to the database.
IBM Notes Traveler 9.0.0.1 Build 201307181414
running on IBM Domino server Release 9.0 HF441|July 23, 2013 on a Windows/64 (2 Processors) platform
using database schema 9.0.0.1.20130514