The specs are for 128Kbps bit rates and for 4 minute songs...bump that up to 256Kbps and you chop it in half... that could be (part of?) your issue.
Reserved space also contains games (if you installed them) and device firmware...but shouldn't be more than a few hundred megabytes...
Playing with reserved space settings doesn't cause it delete stuff though...you can drop the allocation setting but it won't actually go below what it needs... are you sure you didn't also play with your sync settings?