Hmm, that is odd... my dealings are a bit different. I have no problems with AOL and Yahoo.
But even after being "Partially" white listed with hotmail and even getting on their feedback loop system, they continue to give me delivery problems....
Anyway back to your actual post. The only way I can see doing this would be to move All your subscribers to a new list and asking them all to re-confirm. Dean may have other thoughts, but I can't see any other way.
I think a better solution would be to simply get your email delivered to the inbox first.
Here's a thought and what I did to kind of help with hotmail.... On my sendmail, I made a queue group for hotmail and simply /dev/null'd all hotmail messages, basically didn't send them any mail at all for a few days. This made hotmail like my mail server again. I then re-turn on their queue group and mail gets through for a bit.
The trick I guess would be in that time to get them to completely whitelist you... Maybe that'll help, maybe not...