Question: I published an app to the android market about 3 hours ago and it shows up when I got to <https://play.google.com/store/apps/details?id=my.package.name> but it won't show up in the search. 

Also, when I am not signed into google it will appear if I go to <https://play.google.com/store/apps/details?id=some.package.name&feature=more_from_developer> however if I am signed in it will not appear in that list either. 

In both cases, signed in or not, if I go to the apps page directly ( <https://play.google.com/store/apps/details?id=my.package.name> ) it will appear and say that it IS compatible with my device. What is going on in the market? Is this normal behavior?

Answer: 
I also experienced this with some of my apps. It seems that there are some kinds of caching strategies in place that prevent the item from appearing. 

Just wait another couple of hours and check your application again. 
As long as the market says that the app is compatible with your device there shouldn't be a serious error.
Usually it start reflecting in couple of hours but sometimes it can take upto 6 hours or more after publishing it to market.