I use a Sony Minidisc for my lighter recording jobs. They ARE available at the Best Buy stores near me - look in the area around their WALKMAN-type devices. HOURS of recording time with a single AA battery and very good audio quality. Only the more expensive units have mic inputs. Media is not expensive and it can be recorded many times over.

The one down side? No digital transfer out. I have to play it back into my computer realtime to edit the material. I still use studio-type microphones and a small mixer with mine, so it isn't something I stick in my pocket to record a concert.

MP3 compression has a pretty significant quality hit and is very depenent on the quality of the MP3 encoder. I would avoid devices that record MP3 format files.