You sure it got deleted? Check if C:\Program Files\MessengerPlus! 3 is still there, if so doubleclick MsgPlus.exe to start it up again. Then restart MSN Messenger. For some reason MSNM could have been started up before Plus!
What you might wanna do in this case is change the hooking method of Plus!. Set it to "alternate mode" if you are on Win XP, set to "default forced" if not (plus > preferences > general > miscellanious), make sure Ad-Watch is disabled when you set this. This will make sure that Plus! is started before (default forced) or directly with MSN Messenger (alternate mode). If this still aint enough set MSN Messenger not to automaticly run when you log on to Windows (Tools > options > general) or change the following registry key:
HKCU\Software\Patchou\MsgPlus2 DelayedSignin dword 0
You can use this setting to make Messenger automatically sign-in after the specified delay (expressed in seconds). Set the value to 0 to disable the feature. To use this feature, you must disable the auto-signin option of Messenger.
If it's truly deleted disable Ad-Watch when you install Plus!
What Ad-watch does is prevent writing in the registry, that's why whatever you install with it running it won't stay (unless it won't need registrykeys ofcourse). Install Plus! without its sponsor...it might have detected that and therefor uninstalled Plus! entirely (it prolly doesn't know how to make use of the Plus! uninstaller wich has the posibility to uninstall the sponsor only). Make sure you are on an account with adminpriviledges when you install Plus!.
/ 
