So far we have been advertising at findmyhosting.com only. We now want to look for new avenues and increase the current client base.

I was wondering if any body had any experience with HostIndex?
If yes, then how was the return on investment?

Do a search, there have been lots of people experimenting with HostIndex and others. Usually they can break even from what i gather. Just depends on how long you can hold onto those customers!

I wouldn't recommend going only with hostindex.com - there's a very long list of directories you can try.. check out:
hostdirs.com

Good luck

I think it all depends on what types of customers you want ; ones who actually know about hosting , or "fresh leads" from newbie site owners.