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.