windows live messenger substitute

I'm looking for program that can replace MSN and few other communicators with one application
the only important thing that it have to contain is message history

OK OK
I have read few possibilities then I will ask:
which one have achieve/message history
do this program have advertisements?
I want especially replace MSN but the person that I'm talk with using custom icons. is this going to be shown properly?