OK, so this issue has been driving me nuts for ages, and for some reason, I could never find a good answer. The issue is that while some of my ICQ contacts show as online, most of them do not, even though I know they are available (and I can chat with them). Google served up some choice results today, however. Turns out, most of the contacts simply had not authorized me to add them to my contact list, because I had never requested authorization. In Miranda, the solution is to a) add the contact to your server list, and b) request authorization, which is accomplished by right-clicking on the contact from the list.
There could be other causes for this issue, but this is what worked for me. Enjoy.