I guess I never posted an update - after about 4 weeks I tried using my secondary e-mail address to contact facebook via their deactivated account form. Within about 90 seconds I got a response asking me for a response to a private question. I gave the answer and within a few minutes my account was restored.
The only thing I can think of is that they assume that if your account is compromised, so is your e-mail address. I have to wonder if there's some "social" way they can use your friend list to vouch for you.