Turns out that there's a URI structure for querying Apple's store, and that all data returned is in XML format. So armed with a HTTP engine and an XML parser you can build your own iTunes search system. It's not finished yet, and Tim identifies some definite issues that need to be sorted out, but there's a web services API under here (using a similar REST approach to Amazon's).
Here's a sample query:
Just click on it to see the XML results and laugh at my taste in 80s prog rock.
Now how long before Apple publishes the APIs?