I had this problem on a customers laptop with Vista Home Premium and Microsoft office 2007 Enterprise.
I've often seen similar errors with Office including things going wrong with Word, Excel, basically any Microsoft Office application.
Nearly all of these errors can be solved by allowing Office to re-create it's profile folders. I fixed the same problem you are having with this procedure...
1. Close all office applications
2. Browse to and RENAME the following folders (do not delete them if you wish to avoid losing any emails and address books). I normally stick an _ on the end to make it "foldername_"
For Microsoft Outlook...
For other Microsoft Office Programs...
3. Open problematic application (Outlook in this case)
The next problem you will have with OUTLOOK is your Personal Folders file will be new and therfore empty (none of your old emails, calendar or contacts in there!).
Don't panic though, all you need to do is the following...
1. Open Outlook
2. Go to File>Import and Export...
3. Choose "Import from another program of file" and click next
4. Choose "Personal Folder File (.pst)" and click next
5. Click the browse button and locate the folder that you previously renamed
6. Choose the "Outlook.pst" file (which should be more than 1KB if it contains anything) and click the "Open" Button at the bottom
7. Click "Next" and then "Finish" and watch all of your lovely emails, calendar appointments and contacts fly back into your active profile!
Hope that works for you guys.