The best answer I've discovered so far, in hopes that it helps someone else:
As far as I can tell, the key issue is whether the CSS file (not the font file) is loaded cross-domain. If I load the CSS file with the @font-face declarations from my static assets domain, nothing I do will make the fonts work in FF or IE, regardless of the access control headers. If I load the CSS file from the same domain as the page, or I just move my @font-face declarations into a style block in the page head, then it works in all browsers (I can even load the font files cross-domain as long as I have the access control header set).
To summarize: AFAICT, FF 3.5 and IE 8 will refuse to honor @font-face declarations in a cross-domain-loaded CSS file, no matter what.
I would love to be corrected on this if anyone knows better and can point out what else I might be doing wrong.
Indeed, I was wrong. It turns out the CSS-compressor we were using for deploying assets to be served from the dedicated domain was wrapping the entire chunk of CSS with "@media screen { ... }". I carefully compared the @font-face rules to be sure the compressor didn't mess with them, but never checked the very beginning and end of the CSS file to catch that wrapping. When I switched to serving same-domain, that wrapping didn't happen.
As it turns out, IE and Firefox do not honor @font-face declarations wrapped inside @media: Safari, Chrome and Opera do.
Sigh.