Different MSN Messenger accounts could use different relay servers somewhere in the chain, although they all start from the same server...
Also, this has got nothing to do with Messenger Plus! being installed. Messenger Plus! doesn't do anything which prevents or tampers with the connection to the servers.
Anyways, what you could try is to remove the cache directories of MSN Messenger of those "faulty" emails and to remove the per-user settings of those "faulty" emails in the registry:
Deleting the cache directory of MSN Messenger
All the local cache directories of MSN Messenger and your MSN Messenger accounts can be found in the
Application Data directory of the account you used to start Windows. These local cache directories hold information like your display pictures, custom emoticons, downloaded winks, etc.
The directory can be hidden (by default it is), so make sure you have selected to
"show hidden and system files" in Windows Explorer
(My Computer > Tools > Folder options > Appearance > Show hidden folders (or similar)).
The directories are located at:
For XP/NT/2K:
\Documents and Settings\xxxxxx\Application Data\Microsoft\MSN Messenger
For 9x with profiles:
\WINDOWS\Profiles\xxxxxx\Application Data\Microsoft\MSN Messenger
For 9x without profiles:
\WINDOWS\Application Data\Microsoft\MSN Messenger
In short/universal:
%appdata%\Microsoft\MSN Messenger
Where xxxxxx is the name of the account you used to start up Windows with.
Under that directory there are several subdirectories for each MSN Messenger account you ever used. To find the correct subdirectory for the MSN Messenger account in question you can use
Choli's MSN ID Tool or the
online tool/script of Segosa. Thus...
Deleting the cache directory:
- Make sure MSN Messenger is completely closed. If not click the MSN Messenger icon in your system tray and choose "Exit".
- Navigate with Windows Explorer to the local cache directories of MSN Messenger and find the subdirectory representing the MSN Messenger account in question (see above).
- Remove that subdirectory.
Note: This will also remove all your stored display pictures, custom emoticons, winks, etc.
- Restart MSN Messenger and try to sign in with the MSN Messenger account in question.
Removing the per-user settings of MSN Messenger in the registry
If the above didn't work, your last option is to manually remove the settings of the MSN Messenger account in the registry (and thus resetting them).
The per-user settings are stored in the registry at:
HKEY_CURRENT_USER\Software\Microsoft\MSNMessenger\PerPassportSettings
If you navigate to that registry key you'll see several subkeys. These are again those special MSN ID numbers talked about in the previous section. To find the correct one for the MSN Messenger account in question, use
Choli's MSN ID Tool or the
online tool/script of Segosa. Thus...
Removing/Resetting the per-user settings:
- Make sure MSN Messenger is completely closed. If not click the MSN Messenger icon in your system tray and choose "Exit".
- Open up your Registry Editor (Start > Run > regedit.exe)
- Navigate to the registry key shown above and find the subkey representing the MSN Messenger account in question (see above).
- Remove that specific subkey.
Note: This will remove (aka reset) all your stored user preferences for that MSN Messenger account.
- Restart MSN Messenger and try to sign in with the MSN Messenger account in question.
If all the above fails
Perform a global cleanup/re-install of MSN Messenger.
This means:
- Uninstalling MSN Messenger (Start > Settings > Control Panel > Add/Remove Programs > MSN Messenger)
Note: do not choose "repair".
- Removing all the cache directories of MSN Messenger in case they still exist. This means completely deleting %appdata%\Microsoft\MSN Messenger.
- Removing the registry keys if they still exist. This means completely deleting:
HKEY_CURRENT_USER\Software\Microsoft\MSNMessenger
and(!)
HKEY_LOCAL_MACHINE\SOFTWARE\Microsoft\MSNMessenger
- Reboot your computer
- Re-install MSN Messenger
- Reboot your computer again
- Try to sign in with the MSN Messenger account in question
If it still doesn't work
Contact MSN Messenger about it and explain your problem in great detail:
http://messenger.msn.com/help/contactus.aspx
PS: please don't create new threads about the same problem. Simply post again in the original thread if you got more to add or if there are new developments... A request to merge the two threads has been made...
/ 
