After banging my head on this for 3 days with no results, I took the production store down for about 6 hours :(. I dismounted the store and copied the files elsewhere for an offline backup. Then I restored the entire old from tape and exported the mailbox I needed (had to run a eseutil /p on the store to fix the dirty shutdown). Then I copied the offline store backup back in and brought the server back up. What a pain, just to help a CEO who accidently deleted a few emails.
thanks for the ideas Steven even though they didn't help in the end.