Using VBR encoding on my system (PIII 800/256MB) I typically encode at something like 5/6x - so 1 minute to encode a 5 minute song. Ish.

I use LAME exclusively.