Outlook is amazingly bad when it comes to having to share it's files with any other process, even sync. So it could be related.
One thing you can try is to back up the old .pst, delete the profile/.pst and make a fresh one, then import all the emails/contacts back into the new .pst. Outlook in it's infinite wisdom will stop auto-suggesting addresses from the newly imported contact list, so you will have to go offline, then try to send an email to the entire contact list, then delete the email from the outbox to get it back suggesting properly.
In my case, the user's default save directory registry entry was wrong, so Outlook somehow broke while saving something and kept corrupting the .pst, and would keep breaking it soon after making a new file and copying all the old information to the new file.
Desktop: FX-8350 | 32 GB | XFX Radeon 6950 | Windows 7 x64
Laptop: i7 740QM | 12 GB | Mobility Radeon 5850 | Windows 220.127.116.11.1 x64