I ran into the same thing but my storage was listed as 400 GB on a 500 GB internal SSD. What it was was I had rebuild the mailboxes several times in the past trying to get smart mailboxes to work correctly and that added enormous amounts of apparent storage, so much so that I could clone my 500 GB drive to an external 1TB drive.
The culprits were folders titled Data_Rebuild. The only way I could find them was to use the shareware app Find Any File to search for folders like this:
1 - Name is Data_Rebuild
I then dragged those folders from the search results window to the Trash bin and emptied it. They were recreated but with zero size.

FAF can search areas that Spotlight can't like invisible folders, system folders and packages.
Give that a try and see if there's any improvement to the storage situation on your Mac.
