Sounds like you are right about Audacity - it does recompress. You have to "export as" to create the output file, and it uses LAME to encode.
Has anyone tried a tool called mp3DirectCut?. It is billed as "a non-destructive audio editor and recorder for MP3/2. You can directly cut, copy, paste or change the volume with no need to decompress your files into a pcm format. This saves encoding time and preserves the original audio quality, because absolutely nothing must be re-encoded".
It is freeware - I've never tried it, but it might be worth a go.