I don't see how this can be a Messenger Plus! issue though...
Anyways, first make sure in Windows Live Messenger that the option is checked to show the "contact has added you" popup:
Though, if that option isn't ticked, people should normally be able to add you immediatly.
This more sounds like an issue with Messenger itself.
PS: yes, before you are able to use your non-MS email in Messenger, you need to register it to be a
.NET Passport or
Windows Live ID. If you don't do that, you can't change your screen name (and 'not-registered' will be displayed).