Problemas con acentos en formulario de contacto

A ver si alguien puede ayudarme porque me estoy volviendo loco.

Tengo un sitio :

Seguros Caser | Tenemos tu seguro

En el sitio tengo una página con formulario de contacto, que es esta:

Formulario de Contacto | Seguros Caser | YCC Seguros

Esta página, como todo el sitio, está programada con "UTF-8" y en los parámetros del formmail de esta página tiene puesto el parámetro "accept-charset="iso-8859-1" para que acepte los acentos y la eñes en el formulario.

Resulta que la mayoría de las veces el formulario llega bien y otras veces mal. Por ejemplo:

"Solicitud de Información de la Web"
"Solicitud de Información de la Web"

El caso es que no entiendo por que pasa esto ya que es el mismo formulario siempre y con los mismos parámetros.

Para mayor desconcierto me pasa con IE11, Edge y no pasa con Chrome no Firefox.

¿Debo cambiar o añadir algo?

Gracias.

Y has comprobado que también sea así en el script de FormMail? Que tenga el header necesario.

¿Te refieres al formmal.cgi?

El html lo tengo asi:

<Form method="POST" action="http://www.yccseguros.es/cgi-bin/FormMail.cgi" accept-charset="iso-8859-1" style="background-color:#EAEEEA">

Puedes probar el en ciclo del if donde haces el envio if (mail($to, $subject, utf8_decode($message), $header)) a ver si funciona. En resumen usas el metodo utf8_decode($message) a mi me funciono asi, cuando me paso esto mismo una vez.

Yeison, perdona pero no lo veo. Yo utilizo un cgi en que no utilizo los parámetros que comentas.