I'm not sure how exactly the spam is getting through to you. You say you have some forms of validation which I think should stop some form spam bots but some of them will auto fill out fields and then submit. Are you getting spam email sent directly to your PHP $SendTo address or is it form spam.
In any case I also use a PHP mail form but I also encode at least my submit button on my web form page using the Hive Enkoder. see link below. I just copy my submit form button HTML code into the advanced enkoder area and get the scrambled code, paste into my HTML page to replace my submit button. Downside is only site visitors with JS on will see the submit button but you can always have a "no script" message. Haven't had any spam come through with this method.
Hivelogic - The Anti-Spam Email Address Enkoder Web Form
This might be of some use to you (or others). All the best