If you log in to the Androind market form the web and view My Market Account, do all of your apps show up there? Are you flashing between different ROM images? Each ROM image will give your handset a device name, which can be different from ROM to ROM. This could be why you are not seeing all of your apps via the Market app.
The Android Market seems to support a single account on multiple devices, so if you have paid apps on your phone and you buy a tablet, the paid apps will also be available on your tablet. I'm not quite sure on how to get your apps synced up though, in the event that you device name changed. Maybe someone with more knowledge of how this process works can explain it further (or better).
As a saide note, I have always used App Brain to ensure that I can get to all my apps, especially since I flash through a lot or different ROMs. Now that Google has attempted to make the Androind Market web based, they seem to be running into a lot more problems like this. Via the Androind Market web page I still see old uninstalled app as installed! I contacted Google support about this and haven't get a response back yet, but it seems like there are lots of people having these same kinds of issues.