You wont have that problem with Yahoo Messenger if you remove a small .exe file from the Yahoo Messenger directory called "yupdater". Once that little bug is out of there Yahoo can't nag you to update. And the messenger will still work (I'm using an old version of YMessenger right now as a matter of fact- on my 98 box).
I'd love to find a workaround for MSN myself. I need it on this older puter, but like you I can't find an older version that will run. I get the same "download the upgrade" nag.
I've got the newer versions on my XP laptop, but to run them on 98, I need an older version because they require less RAM to run.