I had a situation once, not the same, but we resolved issues by using exmerge to extract healthy data from one IS and then recreated and re-imported the data to a second IS.
Exmerge breaks the single instance, so the IS will typically increase in size by anything from 60% to 200%, depending on the exact content.
A similar option here, depending on the version of Exchange would be to create a second storage group with a new mailbox store, and use the move mailbox wizard. This in theory will only move the mailbox data that you are seeing in ESM, and whatever data that we are not seeing will be left behind. Move mailbox will retain single instance. Just checked your first post, SBS runs Standard edition, so this ins't a usefull suggestion sorry.
We're missing something obvious. Did the last online backup run. The online backup backs up the database 4k (1 page) at a time, the backup job checks the physical page number, the logical page number and performs a data checksum, it compares the calculated checksum with the checksum in the page header, and verifies that the logical page number is the physical page number -2, (the first 8k or 2 pages are the database headers) Then it backs up that page, and moves on to the next.
Bottom line, if the online backup has run, at a page level the database is healthy, there is no page level corruption.
At the next level up, Eseutil or Isinteg should fix any other issues, Eseutil is a little more severe, it simply eats corruption, it's more of a surgical excision of bad data, and you can have a situation where the page that Eseutil removes is the top of a folder structure, in which case you may have lost an entire folder or even a mailbox.
I always tell people that 90% of the time Eseutil or Isinteg will fix a problem, but 10% of the time they can make it 90% worse.
But we've got a situation here where Exchange thinks it fine, so chances are we're missing something.
Over the last number of years I've learned to give Exchange a grudging respect, it's usually doing what you've asked it, in many cases you just have asked it to do something odd...
Here's one out of left field...
support.microsoft.com/default.aspx/kb/891789

Yes I really think it's something obvious too.
We inherited this server and installation from their previous tech support company. There are a few other oddities in the system too.
The system is backed up using veritas, but only certain mailboxes are backed up as the size of the back up is quite large (again not my preferred way of doing things).
I will have a read of the article and run the eseutil /d and stuff as suggested by brettjo

My colleagues Anne and Mark are interested in this problem now - which is great, becasue they can read 0's and 1's as they flash past them encased inside a cat5 cable, that's how good they are.... but anyway, here's what Mark said...
Restrictions is looking the most likely;

From the space tree usage;

STM free space;

105135 + 49027
free + *reserved = 154162 pages OR ~602 Mb

*We include reserved in our free space calculations as the reserved field highlights that Ex IFS has a page reservation. These will then ultimately be released back to the database as white-space and will not include any data and thus are free.

From the EDB tables of interest, rather boringly the largest tables are the attachment table (well known as 1-23) and the MSG table. What's unusual here is the Msg table is actually larger than the attachments table.. not seen that before.
1-23 Tbl 239 3532575 2-m 4011299 13 LV 240 3532576 1-m 3481381 2

1-B82 Tbl 1113 5440181 8-m 413992 10

Msg Tbl 66 711 2-m 5790296 8370 LV 67 712 1-m 3611953 9316

Free space in EDB = 22541

Free space here is flagged as only being ~88Mb

There are a few things that can lead to this type of bloat having lots of "empty" folders can cause overhead. Even if there is no data stored in the folder i.e. its last 2 columns above show as 0 0 its still consuming space, so the sheer act of creating folders does use space. That been said they use 12 pages only (folder + indexes) so you would need 75k to get around 3.5Gb of bloat. Here they only have a couple of thousand, so this is not the case.
An Isinteg -dump will give us some more clues
And then Anne said, "Just had another look and noticed what looks like one huge folder (1-b82) table that is 1.6 Gb....might be worth checking that out with an isinteg -dump"
So, if you can try an isinteg -dump as requested I'll get them to take a look at it for you.
Greg

Hey, there are 10 kinds of people in the world...
Those that understand binary, and those that don't...

Wow thank you guys for all this help. Need a bit of time to digest some of this information.
*crossed fingers on finding a solution*

/dump sounds like it is going to show where and how much but may not reveal why.
Sounds like a move mailbox would be helpful. I'm slightly concerned about the comment of Veritas and that you are only backing up certain mailboxes. Are you not backing up the whole IS?