I believe that most UAV designs for extra-terrestrial missions are designed around the use of airships rather than more traditional airplane or quadrotor designs. An example of initial research in the area is the Titan Aerobot [1]
Much though I love the idea of extraterrestrial airships, wouldn't an airship be even less effective than heavier-than-air machines in an incredibly thin atmosphere like Mars'?
Airships would be harder to make work on Mars, but once you have it working you would almost certainly be in a better position.
Also, Wolfram Alpha peggs the air pressure at 39km on earth, the height Felix Baumgartner jumped from, as 330 Pa. It has the atmospheric pressure on Mars (presumably the average at the surface) as 650 Pa. So balloons that will float in that, at least at a low altitude, are not beyond our engineering grasp. (and unmanned balloons on earth have gone down to as few as 55 Pa http://en.wikipedia.org/wiki/High-altitude_balloon).
You are very right - I forgot to mention those. They tend to be a lot more feasible than fixed-wing aircraft, and their ability to land and take samples makes them even more useful.