I've spent a long, long time searching for a viable, long-term fix for this problem; though I'm beginning to believe that Google Play (or Google Play Services) is to blame. I recently factory reset my phone running KitKat 4.4.2, which has both 16GB of Internal Storage (not an internal SD Card) and a 16GB external microSD card. Even with over 12GB of space remaining (after the factory reset, I was free to download apps from the store with no errors for a while, though it was visibly running a different version), it gives me this error. This is 12GB of Internal Storage, I have over 7GB more on the SD card.
I'm currently at a loss about this. I've attempted to rollback both the Store and the Services apps, and it only clears me to download apps for 5-10 minutes (if that) before giving me the same old error. “Error while downloading There is insufficient space on the device”.
Update: While writing this question up, yet again I attempted to download three apps. The first proceeded through the process without any issue (keep in mind that I had not changed anything since the last time an error was encountered - I simply unlocked the phone and clicked install on the already-open Play Store page for Facebook Messenger), while the second and third spat out the same old error.
I have attempted to clear my cache/move it to another partition, clear the data on both the Store and Services apps as well as the caches, and several other things. APK files never fail to install when attempting to install from an external source. This issue is also not local to this phone alone, my previous model did the exact same thing without the allowance for one download that I just experienced.
Edit regarding "duplicate question": Whether this is a duplicate question or not, I have found no valid solution for this, regardless of how many threads I have looked at and how many different methods I have tried. I've purchased a new cellphone to try and bypass this error ffs. It is not my home internet, as I have attempted to update apps and download new apps from both my mobile internet connection and from several (more than five) different internet sources; inclusive of a USB-tethered internet connection shared from both my computer and a friend's computer. I would like to state that this question is different in the light that I have tried and exhausted every method I have come across, without a single ounce of lasting success.
To put it bluntly, I think that Google needs to get off their asses and fix the problems that so many people are so blatantly reporting.