Well it wasn't the obvious reason this time, you know, too many e-mails that I just haven't read or being a pack rat of large e-mails... Turns out a ton of space was being taken up by a magic folder called "Sync Issues". I've seen it for a while now and have noticed it size is large but couldn't find it so I kept deleting other stuff to keep under our mail box size limit.
Finally today I got tired of it and tracked down the answer - it's a folder that only shows up in Outlook Web Access - it will NEVER show up in the Outlook client. Turns out I had a few conflicts...
All told this was taking up several hundred megabytes of space!
I found an article on the MS Office site here that explains it in more detail. The article says this about conflicts "Contains all the multiple copies of conflicting items in your mailbox " I'm not surprised I have some conflicts considering I sync multiple machines and a mobile device with the mailbox. What surprised me was I had to go to outlook web to find it! After a quick look I made the decision enjoy weekend over review 10,000 items right click - > delete.....Problem solved.
So check your Sync Issues - never know it might be taking up a bunch of your space! This applies to you if you use any version of Exchange Server 2000-2007 apparently.