I had the opposite issue yesterday with Labyrinth LE. Saw it on itunes in the app store, but when I searched for it in the app store from the iphone, it wasn't there. When I checked an hour later it was there.
So apparently the app store in itunes and on the phone aren't pulling from the same database, which is kind of strange.