You can use Sphinx and delegate all search queries to Sphinx. It will, however, create its own indexes and what not so the whole thing won't be storage effective.
The other solution, and this is by making an uneducated guess, is that you could pull out data of interest out of the XML (such as this shipment number that you mentioned) and store it in another 1:M table and perform searches based on that.
Also, if shipment number is entered partially, and I'm guessing again that your users will enter only the beginning or the end of the string - you can use methods such as indexing pieces of the string and reverse-indexing pieces of the string.
Example: shipment number is 123-456. Your 1:M table would contain index on '123' and '654' so you can avoid LIKE '%%' searches.
However, seeing it's a hassle to do this only for one thing that might be of interest and we're talking about 30kb XML here so there's plenty that could be of interest - I'd think about delegating searches to engines such as Sphinx and ease up the coding hassle I'd be looking at.
Maybe someone more experienced has more elegant solutions tho, I wish you good luck with the project