Como estilizar una validación nativa de HTML5 con CSS3?

[OsquiB]

Hola gente tengo una pregunta:
Necesito validar un formulario de registro para una web, en un principio pense hacerlo con JS y PHP pero dado que JS se puede desabilitar me parecio mas rapido y practico validar el formulario de forma nativa con HTML5 y PHP. Aparte me gusta como lo hace :P
El tema esta en que quiero estilizar a mi gusto el mensaje de error, alguien sabe como hacerlo ? y me explico mejor:

Por ejemplo en IE, al completar un campo con caracteres no validos, el campo tiene un borde rojo horrible y ademas sale el cartelito o popup o como lo quieran llamar. En google chrome no sale ese borde rojo pero sale una mini imagen con un signo de exclamación (!) junto con el mensaje de error.

hay alguna forma de editar eso? es decir, que no salga ningun borde en ningun navegador y que el mensaje sea estéticamente igual en los navegadores ?

Si alguien conoce una forma mejor de validar un formulario que me diga :D