I just visited the Market so I know it is available. I've not used App Brain so I do not know how it works but it may capture the market apk and if you deleted the apk may have been deleted. Just a thought.
The market has been wonky for me today also.
Kept downloading lite versions (of paid apps) I had recently deleted.
Took three attempts to down and install the new Gmail app.
stock Droid 1.
It's also been rather wonkified for me these last 24 hours as well. It'll run real good for a short time then go all bizonkles. I'm guessing it's simply a matter of overload due to all the people getting the new Gmail app and that ninja game on the front page and stuff like that. Give it a couple days and if it's still kerwiffy for you then we can proceed to the next phase of troubleshooting.
I'm not rooted, and I just checked my work mates incredible and his market works fine, oh btw i have a Droid 1. Where would on look to fine the apk file?? how can it be reloaded??