This isn't strictly robot related, but have you seen the South Leicester Aeronutz website?
There's some really amazing radio controlled creations on there. Most of the creations use very thin (2mm) foam walls and tiny pager-type motors to turn the prop. You can purchase super-small (under 1cm squre) radio receivers from Micro Flier Radio. For $20 you can get a 20mm x 20mm x 5mm lithium polymer cell with 90mAh of power. South Leicester has a nice writeup on using capacitors to power these vehicles. The site seems a bit dated (last posted newsletter was from Feb. of 2004) but there's still a good bit of inspiration to be gained.
What if you put a IR transmitter on one of these and used several base-stations to track its location for computer control (read:
robotic)? Now all you need is a really really tiny camera to take aloft.