Hey Brian. I have some answers and updates for you.

Answers to questions from the previous reply:

I don't see any archive folder listed in Mail Folders pane on the left. All
I see is Outlook and recovered outlook with all its sub-directories i.e.
inbox, sent items, deleted items..etc..

The way you told me to look for type of .pst its using is didn't match the
way I found it. I first selected the inbox, then went to File -> Data
Management -> Settings, then on the format line it says Personal Folders
file (97-2002). It looks like its using 2000 format still eh?

Updates:

I'm able to remove old messages from the Inboxes, which was the original
problem all along, then
able permanently delete them.

Here's some more questions for you.

After I have removed messages from the oversize inbox, shouldn't .pst file
size shrink too?

Also you said, if outlook was using the 2000 .pst file size, I should change
over to '03 since its much larger, right? Well how do I do that? Does that
affect the messages and contacts that's already in there?