You could just use one of the many alternate ICQ clients and not have to deal with the ads at all. Trillian is free and popular. GAIM is popular under Unix, and they have a Windows version now. It's also free. Miranda looks nice and is free.

But, as to your problem, assuming you've made no configuration changes, I would bet that it's a change in IE. Have you done any Windows Updates lately?