I tried out Yahoo's address book, and it seems rather extensive, and the notes are searchable. The key for what you want to do is to find good keywords that you can use for searching as well.

Also, although I haven't had time to check it out, I just found:
zexer.com.

It seems to be rather attractive, but I don't know how flexible/powerful it is. :-) I'm about to look for online CRM, which seems to be more what you need.

-Jon