Okay I figured out a bit of a fix that worked for me that I haven't seen mentioned elsewhere.
If you go to Apps > Remove Apps > All, you will have a list of everything installed on your phone. If you click on any app, say Facebook for example, you will see it has stored 'Data' included in it's total size, I have 716KB listed here. If you press the 'Clear Data' button, you get this message:
"All of this application's data will be deleted permanently. This includes all files, settings, accounts, databases and so on."
Now obviously you will not want to do this with some applications (like facebook, if you use it, and who doesn't?) because as far as I understand, it is like resetting the app to it's default settings. You will want to keep the data there.
I took a look at my recently installed TED app, and discovered it had 3MB of Data on it. Now that's pretty crazy, because I've only ever opened it once, and I didn't go into the settings at all. So I press the Clear Data button and free up the 3MB of space. What is most interesting to me, is that this app has been moved to the SD card, and yet this Data is stored on the phones internal memory.
While typing this message I tried re-opening TED to see if anything would mess up. Nope. It works fine. I go back into Remove Apps and discover it has rebuilt the Data to 3MB again. Okay. So that's pretty crap. I was able to install some updates while that 3MB was gone, however, so this is still useful, as sometimes you just need to push the free space over 15MB to install or update things.
In my search through the all apps list, I did happen to find several pre-installed applications that I never use that had upwards of around 4MBs in total that I safely removed. Things like HTC Hub, and the Stock app that I must have opened once and decided never to open again.
The storage issue is my biggest problem with the Wildfire S and I was happy to discover this, so I hope it helps someone else out there. Just don't clear data of anything you're unsure of