Então, coloquei um quinto parâmetro na função mail() que tem o poder de informar o Return-Path.. Vejam como ficou:
mail($email,'Assunto','Minha mesagem',$headers,"-fcontato@emaildocliente.com.br");
Assim o email foi pra caixa de entrada!!!
Mas agora eu pergunto.
Como setar este parâmetro automaticamente?
Gente, parece que esse é um problema bastante comum..
Vejam: http://thesystemadministrator.net/cpanel/using-5th-parameter-in-php-mail-function-on-cpanel-server
Muito obrigado!!