Last time this came up someone pointed me at the new generation of ultra-low-power ARMs:

http://www.atmel.com/products/microcontrollers/arm/sam-l.asp...

35µA/MHz, so with careful selection of peripherals you probably don't even need a whole milliamp.

Designing microamp-level systems can be interesting. From http://www.ganssle.com/rants/leaks_and_drains.html :

  I put one of the boards under a microscope and looked at 
  some of the ancillary parts. There's a 22 uF decoupling 
  capacitor. No real surprise there. It appears to be one of 
  those nice Kemet polymer tantalums designed for high-density 
  SMT applications.
  
  The datasheet pegs the cap's internal leakage at 22 uA. That 
  means the capacitor draws a thousand times more power than 
  the dozing CPU.

Yes, I play with little robots built with microcomtrollers. For some of our little boards my friends and I make we leave off the LEDs because they consume more battery than the CPU. (Of course the motor makes up for that quickly...)