As MP3 encoding is frequency-domain-based, could you get that effect even more simply, by just converting back to a different time-domain sample rate?

I don't think so. In that case you would have to play the samples at the new rate or your pitch will change. But our rate is fixed. What you maybe could do is figure out the sample rate you need, and then scale in the frequency domain before the conversion to compensate. It would seem that would be a quite subtle way of changing the speed. (At least, compared to just dropping samples!!). It also makes sense to slow things down with this method, which could be hard the other way, because you have to figure out where and which samples to add.

Or am I wrong?

Richard.