These were the two error messages:

Here are the steps we took to repair them:

Run the Inbox Repair Tool.

https://support.microsoft.com/en-us/kb/272227#Can%27t%20start

• This did NOT work for us.
• After clicking Repair, this tool went into Not Responding status.

Open Outlook under a different profile.

• Control Panel > Mail > Show Profiles
• Select "Prompt for a profile to be used"
• Then run Outlook again. It will give the option of which profile to use.
• Simply doing this twice, and using the "broken" profile the second time, let us use the broken profile. Who knows why?!

Use Archive to break the PST into multiple files.

We did this to prevent future errors from occurring.

https://support.microsoft.com/en-us/kb/2720581#method3

1. Open Outlook. 
2. Select: File > Info > Cleanup Tools (Mailbox Cleanup).
3. Click on Archive in the dropdown box.

Note: To see if the Archive process is running, look at the lower right-hand corner of the Outlook screen.

Compact the original PST file.

Archiving isn't enough. We must compact, lest after archiving the original files size stays the same.

http://superuser.com/questions/287926/pst-file-same-size-after-archiving

1. Control Panel > Mail > Data Files
2. Choose the target data file to compact.
3. Click Settings
4. Choose "Compact Now"

Note: For large PST files, this can take an hour or more, during which we cannot do much else. To check the process, open Resource Manager and view the Disk usage by OUTLOOK.exe. It should be reading and writing from the PST file that you specified to compact.

Our work here is done.