Voice Recorder
I'm not sure how low of a price you're looking for. I just got an iRiver ipf-890, I haven't gotten a chance to use it with a mac (it lives at work), but it has mac software.

I was pleasantly surprised by the sound quality from the builtin mic. The native format is not mp3, but the software you install to manage it converts to mp3 when you download to your computer.

pros:
decent sound quality
reasonably small (bigger than a shuffle, but still only
about an ounce)
sample and bitrate are adjustable on the player
doubles as flash mp3/ogg player
aa or aaa battery powered (can't remember)
the 890 is probably more than you want, but there are
many models, some with line in jacks. price points on
these can be as low as 75USD

cons
primary control pad very small - it's easy to select when
you mean to move up/down a menu or vice versa
requires special software to interface with your computer

Wrote on in Java
This may not be what you are looking for, but I have written a very small voice recorder application in Java. There is also a more elaborate voice recorder (but somewhat buggy) Java application. Do a search for "JavaSoundDemo." Of course, this is all free!

iTalk for iPod
If you already have an iPod, you could add Griffin's iTalk to it.

Just use your phone
Sign up for a free account on Trekmail (www.trekmail.com), then call 415-382-4224 whenever you want to record a memo. It'll record up to 20 minutes of audio, then email an MP3 to you when you hang up.

You can also record telephone calls by adding Trekmail to a three-way call between you and the other party.

Just use your phone
Great idea! But not so great for Brits like me. The international phone calls would end up being a bit expensive, I think... :)

Olympus DS-330 Digital Voice Recorder
Not quite as small as a Shuffle, but close. The Olympus DS-330 has USB download of files, AAA-powered. Headphone jack. We use it for meetings, conf. calls, usability sessions, etc. The files are Transcription-standard DSS format, but easily converted to MP3 as needed. Mac-compatible out of the box. Hope this is helpful.

Olympian Recommendation
I’ll add another vote for the Olympus recorders. I carried a V-90 in my pocket for years and loved the way I could whip it out and start recording instantly. Most MP3 players make you fumble with a menu or endure a long boot-up.

I’m currently reviewing the new Olympus DS-2 for O’ Reilly’s Digital Audio site; the review should be up by May 19. The DS-2 is on the big side, but it sounds far better than typical voice recorders. Nice Mac software, too. I discuss a few alternative models in the review. —David Battino

And another recommendation...
And here is another one, a little late though. :-)

I use an Olympus WS-100 voice recorder that might be to your liking. Anyway, the WS-100 does what I want it to do. It meets almost all of the must have criteria on your list, except for the output file format which is WMA.

For normal use this isn't a problem. When downloading the sound files to my Macs, I use either "VLC media player 0.8.1" to listen to them. To archive them or use them in iTunes etc I use "EasyWMA" to drag-and-drop-convert them to MP3 on the fly.

I connected my Sony studio monitor headphones (I use for sound mixing in Final Cut Pro) and I was amazed at the high quality of sound I get from that little gizmo. It is small (like the iPod Shuffle, and need just one AAA battery. Pull it apart and it is a USB stick. I comes with earbud headphones and a lanyard to wear around the neck.

Hope this helps. :-)

I found a bloody good recorder
I'm no techie, but i had the same requirements except that I have a PC.

I highly recommend checking out the iAudio U2 1GB - it's made by a Korean company called Cowon who specialise in mp3 players, and on their brochures say they have a Quality Voice Recorder, like doesn't everyone else say that too, right?

I initially tried out Creative's mp3 players with built-in voice recorders but they weren't very clear at all, and I'm sure it'll be much the same with other mp3 players because voice recording simply isn't a high priority.

I also considered an iPod mini with the iTalk microphone but it only works on the iPods with docking capability, so not the iPod mini - iPod is expensive and bulky and do you really need so much space??? Besides, I read in some reviews that it takes a couple of seconds before the voice recorder kicks in, not ideal really, especially since you're paying big bucks for the iPod and more money for the iTalk (in NZ they are bloody expensive).

So what about the Ï've never heard about Cowon iAudio U2 1GB? It's got nothing to do with the supercool Irish Band, 1 GB will record for very very long sessions, has adjustable quality recording levels,up to 128-bit, adjustable mic sensitivity levels (10 steps), records directly into mp3 format - which i love, cause it's so easy to listen to on my laptop, and plugs straight into my USB and shows up as another drive. And it has a Li-On battery that charges when it's plugged into my laptop's USB port.

And lastly, which you'll find hard to believe, it's firkin' small!! smaller that a disposable cigarette lighter (slightly shorter, but more boxy, but hey, still bloody amazing, keeping in mind it has 1GIG of flash memory!).

Actually, I won't stop raving like a maniac, because it's really really easy to use, and looks damn cool in black and silver. It's a bit of money at $399 New Zealand dollars, but I'm sure in the US, you can get a good deal for it.

It's new, it's hot, it does what you want, and doesn't cost a lot.

Cowon should be paying me for this...if you get it, let me know how it goes - I'm sure this thing kicks ass over anything else out there, tiny lil thing...

if you want to find a good voice recorder,
Crystal MP3 Recorder and EZ Mp3 Recorder may be the best choice for you.

how about attaching a seperate microphone to the line in of an mp3 player, has anyone ever tried that? That would solve the weak internal microphones most mp3 players have. Something like this

Also this article addresses the question from cnet. iAudio G2 has a usb dongle which is almost as good as direct usb plugin.

There are some who have tried using the iriver 800 series which apparently has speical settings to allow you to do this. The T series is a little quieter when using line in and the mic needs an amplifier. click here

I am on the lookout for a good recording mp3 player with usb plug-in myself.