What wattage should a headphone amp be?
Alfred already explained that for a voltage source (which an amplifier is) you'll have less power at higher impedance, because the current decreases. If your amplifier would be a current amplifier you would get a higher power, because the same current in a higher impedance will increase voltage.  

Citing from this document, because I can't explain it better myself:  


  Headphone manufacturers specify a “sensitivity” rating
  for their products that is very similar to loudspeaker sensitivity
  ratings. For loudspeakers, the standard is to apply 1 watt
  and then measure the sound pressure level (SPL) at a distance
  of 1 meter. For headphones, the standard is to apply 1
  milliwatt (1 mW = 1/1000 of a watt) and then measure the
  sound pressure level at the earpiece (using a dummy head
  with built-in microphones). Sensitivity is then stated as the
  number of dB of actual sound level (SPL) produced by the
  headphones with 1 mW of input; headphone specifications
  commonly refer to this by the misleading term “dB/mW.”
  What they really mean is dB SPL for 1 mW input.  
  
  Think about these sensitivity definitions a moment:
  headphone sensitivity is rated using 1/1000 of a watt; loudspeaker
  sensitivity is rated using 1 watt. So a quick rule-of-thumb
  is that you are going to need about 1/1000 as much
  power to drive your headphones as to drive your loudspeakers
  since both of their sensitivity ratings are similar (around 90-
  110 dB SPL). For example, if your hi-fi amp is rated at 65
  watts, then you would need only 65 mW to drive comparable
  headphones. (Actually you need less than 65 mW since most
  people don’t listen to their loudspeakers at 1 meter.) And this
  is exactly what you find in hi-fi receivers—their headphone
  jacks typically provide only 10-20 mW of output power.  
  
  Take another moment and think about all those portable
  tape players. They sound great, and loud. Why, you can even
  hear them ten feet away as the teenage skateboarder that ran
  over your foot escapes.  
  
  Power output? About 12 mW.


(emphasis by me)  

Thanks to marketing numbers of 100 W amplifiers most people don't realize this, but 1 W is a lot of power for a good speaker. It can give you more than 90 dB SPL at 1 m. At full power a 100 W amplifier just won't break the windows. Claiming to play 2000 W at full power in your living room is nothing to brag about: it just says that you have lousy speakers :-). 2000 W in 92 dB speakers delivers 125 dB SPL, which will turn you deaf in no time. (That may be OK, once you're deaf it also stops hurting your ears. :-)

Further reading
Understanding headphone power requirements