I don't know if anyone has posted this yet as I only checked this page and the preceding one, but CorePlayer Mobile 1.2.1 has an awesome YouTube interface. You can search right from the player itself. Just make sure to go to the Network preference tab and select high quality so you get the h.264 versions of the videos.

Beautiful.