MXTube, an app that allows downloading of Youtube videos in two different qualities (one preferred for EDGE, and one for WiFi), works on EDGE. I checked and made sure both searching and downloading work. It was on one of my Installer sources, but I don't know which. Check the native app board.