This is a problem with the application's files. It's known to delete the contacts without notification or alert.
Create a backup of the database with contacts using the following path:
-
Prior to Windows Live Mail 2011 > Windows C:\Users\<windows username>\AppData\Local\Microsoft\Windows Live\Contacts\default\15.4\DBStore
-
After Windows Live Mail 2011 > C:\Users\<windows username>\AppData\Local\Microsoft\Windows Live\Contacts\default\15.5\DBStore
Copy the file, reinstall Windows Live Mail and then place the database with files back and that's it.