If anyone has not yet solved the problem and would like to do so without external input then do not read this post as it contains some discussion of the method used to obtain the solution.
ThomasScheidegger, having read your solution I am very impressed. I too started to work on it after reading the additional hints posted and quickly recognised the use of Huffman coding in the problem (the mention of 'a paper from 1952' really gave this part away). I also assumed that Wingdings had been used to mask the characters used in the message (admittedly, this was a guess).
Contrary to your method however, I attempted to manually draw the Huffman tree and it's here were it all went horribly wrong for me. With the tree that I obtained the binary code did not lead me to the first message that you received from your program, and therefore I also did not get the second message and ultimate solution.
I really thought I had it solved when I realised the link between the Huffman coding, the Wingdings obfuscation and the binary, hence the earlier post that I made out of sheer excitement. Well done mswanson on creating such a difficult problem. You should refer it to Microsoft's human resources department as an interview question for potential employees.
I have worked out how to solve the problem. I do not have the solution yet but I'm very close and will post it as soon as I am finished.
Edit 1: It turns out I was on the right track but was beaten to the final solution. Continue reading the thread for further clarification.