We have no idea what the actual values of $to, $subject, and $message are. Since we've only been shown partial code, even the content of $message is suspect (as the first mention we see is a concatenation).
The additional headers here seem to be properly constructed. The code even has the original comments directly from example 4 from the mail() function documentation from the php manual.
I find it odd that empty strings are continually concatenated throughout the $message construction and rarely any newline or <br> instructions. Possible that some code didn't get pasted into the example correctly? These are the kinds of things that make me suspect that we are even seeing the actual code.
I just spent three days convincing a person on another forum on another site to stop pasting partial code and to send me a complete file to help diagnose his problem. Once I saw the complete file, the answer was obvious... and not to be found in any code he had originally posted or emailed.
As an aside, I also note that when visiting the OPs site, I get the message:
A Runtime Error has occurred. Do you wish to Debug?
Error: Object expected.
every time I move my mouse over the menu bar on the left. I always get the message twice. It appears to be an issue with the mouseover code and I don't get any imageChange effect. Using IE 6.0.