I install a free app from android market, then I uninstall it. Then I still see it linked to my google account. But after some time, the app is no more linked to my account. Other apps instead are always present under the "Not installed" category... When is an app unlinked from an 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.