Have you tried apps2sd yet?
This happened to me a while back, but i think it's because the apk is downloaded>installation>apk is finally deleted. So during the installation, the apk is still stored on the phone, but deletes it after. That is my theory.
It could also be that the phone is accounting for space it needs to store data from the apps you have and will not install because it will bog down the system.
Anyways, try app2sd.