The earlist version I can find at the moment is MSN MSN 2.5.1 and according the Microsoft website you must have Mac OS 9.2.2 to use this version.
With a program from Gestlab you can change Gestalt information about your computer (such as which version of Mac OS you're running). You'll need to change "sysv" selector to "00000922"
This should let you install MSN Messenger 2.5 on OS 9.1
If you can, you might want to upgrade then you may be able run a later version than 2.5.1. But I do not know this for certain.
According to the website, QNEXT Messenger apparently runs under Classic, though I can not confirm this.
http://www.getfreesofts.com/soft/366...Messenger.html