It's a problem with the Android SDK.
Starting with 1.6, Google introduced screen sizes: Small, Medium, and Large. Our devices have Small Screens (along with the HTC Tattoo). The G1/Dream has a Medium screen, and the Droid/Nexus a Large screen.
The problem is the SDK defaults to Medium and Large screens. It's up to the application developer to test the application for Small screens and proactively add the indicator for Small screen support.
Most developers never bother to indicate the app can run on Small screens, so it gets excluded from your view.
I'm not sure if the small screen thing is linked to the /data or your Google user account. If I knew which, I'd figure out some way to spoof it, so we can get the full market on small screens. If it's on the /data somewhere, then that's a much easier fix.
The fact that clearing your /data and booting up a 480x320 fixes it, seems to indicate it's a value in the /data. It'd be interesting to do a dump of two /data directories with only the market resolution changed and see how they differ on a binary level. Then perhaps we can add a patch to the menu of NoMoRootfs (or a patch that's applied every bootup... or lock down the file that's modified).
If it's on the account, then either you'd have to intercept the Market App's data packet that indicates screen size and modify it proactively, or you'd have to change parts of the SDK to report the screen size as larger than it really is (this would be hard to do because apps use that interface too... you'd have to be able to detect if the request is coming from the Market App).