Welp, smooth move on my part. I can't update any applications in the Market now because I accidentally deleted my android keystore. Does anyone know how I could get it back? I've tried running a recovery program, but for whatever reason it's not showing up.
If you've lost your private key, it's gone forever (unless you have backups).
Maybe worth trying if you can take your existing APKs, sign them with an additional new key and upload them. Then for subsequent releases, you could use the new key.
Whether this really does work in practice, I'm not so confident, but could be worth a try:
http://stackoverflow.com/questions/2881904/how-to-sign-an-apk-with-more-than-one-certificate
You are probably out of luck.
But if it were me, and I knew any bits of the key file at all (such as a header or key name or whatever), I'd immediately unmount that partition and grep the device file for those bits (if you are on windows, boot with a live linux CD).
It probably won't work, but at worst you loose an hour or two of CPU time on a wild goose chase.