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 S3 (Stock, rooted TouchWiz)
Samsung Galaxy Tab 3 7.0 (non-rooted, stock)
Samsung Galaxy Tab 2 10.1 (obsolete, slow, rooted)
Samsung Galaxy Note 10.1 2014 Edition