When is a free app removed from your google account?
Only the paid apps you've purchased will be listed under the "Not installed" category indefinitely.  I believe it takes a few hours (or sometimes days) for the Market app to sync with Google servers to refresh the list of installed apps.