I haven't really used it this yet, but came across it this morning, but wouldn't something like www.meebo.com work for IM'ing on the iPhone? It's a web-based app, so I would think it would.
I'm sure lots of IMing can be done with Safari on the iPhone. I'd probably rather use AIM.com's AIM Express (since at least AOL already has my AIM password).
However, a real built-in app would not only be more consistent and easier to use, it could also (potentially) notify you of new messages on the home screen.
Web-based IM is a workaround, but not ideal.