XML::Parser is definitely the more powerful of the two options, but it's more complex to use. One way to use it is to process the XML as a stream; you give the parser some callback functions to use as handlers, and those functions get called each time a specific "event" occurs in the parser: the start of a tag, the end of a tag, character (non-markup) data. XML::Parser also has "styles" that make it easier to use (like a "Tree" style that loads your data into a tree--although don't expect a nice hash like XML::Simple gives you).

XML::Simple returns a hash reference, so couldn't you write a recursive routine that descends through that hash and does whatever validation you want on it?

There are a bunch of XML modules, and here's a really good article about them: Processing XML with Perl.

From what you said, you may be best off just going with XML::Simple and writing a sub to recurse through the hash.