Regedit:
In the registry under
Computer \ HKEY_CURRENT_USER \ SOFTWARE \ Microsoft \ Windows Live Mail
Create these 3 DWORD entries (were not available for me) or change to 1 if they exist
RecreateFolderIndex = 1
RecreateStreamIndex = 1
RecreateUIDLIndex = 1
Restart Windows Live Mail.