You can do this with Plus! right through your contact list. Right click on the contact name, go to Messenger Plus! Extras > Notifications. Select "Notify me each time" and "Contact's status changes to" and set that as online. That should do the job.
All you have to do is make sure you have Messenger Plus! and the compatable version of MSN Messenger.