AIM does a lot of back and forth data transfering between AOL and you, the end user, so it is possible that a delay could be on either end.
I would recommend GAIM instead regardless of your issue. GAIM is free, no ads, and it supports yahoo, aim, msn, icq, and a few others I'm forgetting at the moment. It also has great plugins for secure messaging, etc. http://gaim.sourceforge.net
You are running up-to-date antivirus software on your system, right? Two friends of mine caught a nasty virus from using AIM and had similar difficulties in communicating... but more significantly just browsing the web. PC-Cillin is my favorite scanner, and it is one of the cheapest. Panda is also very good, but it conflicted with my email client (Bloomba from StataLabs). The two formentioned also come with firewalls, but then again so do Norton and McAfee these days... for a few hundred dollars more.