Si te han pedido específicamente DTDs, entonces ahí quizá es mejor que tires por ese camino, aunque igualmente te recomendaría aprender XML Schema para casos sucesivos, e intentar que el cliente los acepte. XML Schema es una especificación de XML, con lo que la estructura de un Schema es la de un XML utilizando elementos específicos de XML Schema.
Básicamente, con el Schema tú defines qué campos puede y debe tener tu XML, su estructura y los valores que soporta. A mi modo de ver, no es nada complicado. Si utilizas Altova (y quizá también Oxygen, ahora no recuerdo con seguridad) para generar los XSD, el propio editor tiene un sistema de intellisense, si no me equivoco, lo que te puede ayudar a generar un XSD correcto. Eso sí, siempre después de haberte estudiado una buena referencia de XML Schema. Si no, no aprenderás XML Schema.
En cuanto a validadores, he investigado y una búsqueda en Google arroja muchos resultados. Te pongo solo algunos:
http://www.validome.org/xml/ -> Este es el que, personalmente, utilicé yo
http://www.xmlvalidation.com/ http://www.javaview.de/validator/ http://www.stg.brown.edu/service/xmlvalid/
Para aprender, a mí me parecen muy buenos los tutoriales de la w3CSchool, que te suelen ir guiando paso a paso de una manera bastante clara. Aquí estaría el de XMLSchema:
http://www.w3schools.com/Schema/default.asp
Espero que esto te sirva de ayuda :)