There's a third option of sticking with XML, but query with whatever XML API you're using - e.g. LINQ to XML makes queries relatively straightforward in code.
Have you already parsed the text into an XML document?
Are you convinced that this is actually a significant performance bottleneck in your code? (e.g. if you're then talking to a database, then don't worry about this to start with - just get it to work in the simplest way first)
Are the queries always the same, or are they dynamic in some way?
Do you have a test rig with realistic messages and queries? If not, you need one in order to evaluate any answers given here with your data. If you do, I would expect it to be reasonably easy to try it yourself :)
answered 2008-11-10T12:04:25.657