you must have a literal ton of stuff. i only have the S3 but i got 200+ apps/games and still have well over 5GB remaining and never have moved anything to the SD card yet.
Sometimes when an Android phone's cache or dalvik cache gets so full the device random reboots and when you check afterwards (many folks wouldn't even know their phone even rebooted itself) the memory has freed itself.
Samsung Galaxy Precedent (rooted, AreaRom 3.4 , sd-ext w/ 3.65GB internal space)
Kindle Fire (1st Gen, rooted, AOKP JB 4.1, Nova Launcher)
Samsung Galaxy SIII 4G LTE (rooted, Carbon ROM)