I saw this with Skitch yesterday. My guess is that the main iTunes server(s) are different than the mobile ones, and it takes longer for the search database to update on the mobile servers; even though the app is there and available.
I could get to the app's page on my iPad, but only by clicking on the iTunes Store link on the developer's website in Safari. It would not show up in a search. Today, it does.