Intermittent IMs Going to End Users

Recently, we installed an Openfire server on our network and have rolled out a branded Pandion client to about 80 Windows XP-based machines around our domain. The Openfire server was put on a Windows XP SP 3 box itself, with a 2.66 GHz Celeron CPU, 768 MB of RAM, and a 40 GB hard drive. Initially, it appeared there were no issues with the rollout and everyone signed on successfully after we pushed out the Pandion client by hand. However, end users are reporting issues sending messages and certain people not receiving them on their client. It appears to be happening sporadically and to no particular set of users, but certain users are reporting messages are not ending up at their destinations. For example, User A will send a message to User B. User A will see it go through on their IM window, but it will not appear on User B's. I turned monitoring and statistics on the server, and it appears a connection was made between the two and went successfully through. User B, more often than not, WILL be able to send a message to User A just fine. No particular extra settings or plugins were added on the server, it's a stock install.

Our firewalls are Fortigates across our network and it does not appear that any of that traffic is getting held up in a quarantined state or anything like that. Users are now also reporting not having their avatars saved after they log off and shutdown for the evening. Their old set one does not appear after a reboot.

Any ideas?