ICQ (which has always been the best IM chat client) allows you to use their website to search their user database; you don’t have to have the software installed.
There are a few people who I want to look up on AIM, but it seems you have to have the program installed in order to search their database. I don’t really feel like installing it. Maybe I’m just inobservent with regards to their homepage, but can you look up AIM users without having the client installed?