I have a 60GB edb file, and I want to break the database into individual emails. I do not have any of the original domain information, so I can't just fire up a Server 2k8 vm and reattach it there. I have made some progress with a naive approach of stripping binary data (bytes not 0x09, 0x0a, 0x0d, and 0x20 through 0x7f) from the file (went from 60 to 30 GB), then split that at obvious SMTP headers. That approach does not seem to work because Exchange doesn't keep the entire email together in a contiguous block, and it seems to duplicate a lot of the email (this is probably an artifact of treating the entire file as a filesystem, rather than doing something more sensible like letting the filesystem be a filesystem, and just storing the emails in /var/mail or the like).
So, question is: what tools and documents for the Exchange Database File Format are hidden in the world that Google can't or won't show me?
Take a look at Joachim Metz' work. He reverse engineered the edb format and analyzed the exchange database to a limited extend. It's open source and there's even some documentation about the tables and columns:
http://sourceforge.net/projects/libesedb/files/
However it doesn't do more than you have seemingly achieved. It exports all tables of the edb into separate files. You would have to use the provided documentation and compose the emails yourself from the bits and bytes you export from the database. Keep in mind though that the information about the emails and attachements is rather scattered and all columns are rather cryptic in their naming. You have to do some research and reverse engineering yourself to get through this data jungle.
Since the project is open source you can adjust or extend the code and get to where you want to get quite "easily".