Вы смотрели на LINQ to XML ? Похоже, это было бы идеально для этой ситуации, позволяя запрашивать XML с SQL-подобным синтаксисом, и производительность не должна быть слишком плохой для ~ 5000 записей.
Редактировать: Извините, я неправильно понял вопрос - кажется, вы имели в виду 5000 XML-файлов, а не 5000 записей. Тем не менее, возможно, стоит посмотреть.