Insufficient Storage Available During Update Preface (TL;DR)
I know the issue of insufficient space has been discussed in various contexts but I have not found anything that specifically addresses the circumstances and issues that I am facing, so I am hoping to get some feedback that would help me better understand what is going on.
I have an HTC EVO 4g from Sprint running Android 2.3.5 (Gingerbread) which has been unlocked using the Dev patch provided by HTC. Although it is rooted and I can apply a custom ROM to it, I have not done so yet for several reasons I won't get into but my issue should be independent of that. This phone is by far (in my humble opinion) one of the best and most stable piece of hardware that HTC has produced to date and I couldn't be happier with the phone, hence why I have not upgraded to a newer device. I know the older OS is a turn off to many and I agree that I wish I was running a higher version but most of them don't honor the latest drivers available which means you lose 4G functionality among other things. So I have stuck with it for now until such time as an updated drivers are released (doubtful but one can hope).
I have an 8 GB SD card (7.39 GB usable) and 4.05 GB free - since I move anything that has the option to run off the SD card to external storage. I have 500 MB internal storage (427 MB usable) and a little over 60 MB free. I have never had issues updating anything since the space present has always been enough to install or update before moving stuff to free more space.
The problem
Recently when updating apps it often gives me the insufficient storage available message – but it makes no sense to me.
Storage facts:

external SD with 8 GB (4 GB free)
internal storage with 500 MB (60 MB free)
example problematic app: apk size ~6 MB / installed size 11.46 MB

Detailed problem (again: TL;DR)
Specifically the app that is giving the problem recently is Lookout Security &amp; Antivirus which has never been an issue and is only 6 MB and change but it will download it and when attempting to install pops that error. I don't get how a 6 MB file that has never had issue updating on less than 40 MB space is now giving me problems with over 60 MB free? The baffling part is that occasionally it WILL actually update just fine without issue and I have checked my cache and stuff, nothing there, no other apps running that would hog space or anything, so what's wrong? How can I mitigate this? Another bizarre thing that started to happen is that internal apps like Facebook which are bloated on there whether I like it or not and I use rarely are giving me problems too by issuing the invalid page file error. I mean what?
So what's going on here? What is wrong or what can I do to make it right so it stops being stupid like this? As I said, NEVER had a single issue with this phone, EVER, but in the past month it has driven me absolutely NUTS. I have even uninstalled applications that don't provide the move to SD option to free up nominal space and it stabilizes for like 2 days and then bam, back to square one even though it has more space now. I am at my wits end and I would appreciate the help; especially not being a novice this is even more mind boggling to me.
UPDATE: 10/26/13 @7:45 AM
The application updated normally without giving the error and it did so while the internal storage had only 43 MB (as opposed to the 60 MB when it failed numerously). This lends itself to even more confusion as to what is going on. The ONLY thing that was done in the meantime was that I rebooted the phone (actually more like I was low on power, shut it down and when I connected it to the charger, turned it on)
Same kind of a situation happened to my SAMSUNG GALAXY S2 and I could solve it by following these steps:


Open the phone app and switch to keypad.
Dial *#9900#
On the screen that appears, click on the button labeled "Delete dumpstate/logcat".