Often when one encodes to mp3 or another format, the file is lowpassed, often at 16kHz. But the samplerate is still 44.kHz. Would it sound just as good if I just used 32kHz samplerate with 0-16000Hz music?
If one looks away from antialiasing, Nyquists formula: fsample=2*fmax, where fmax is the -3dB frequency, right?

If so, I could then use the same kbit/s as a 44.1kHz file, and get better quality, since a 44.1kHz uses more bits just because it's sampled 12.1kHz more times a second than a 32kHz file. Or is this totally wrong?

Yes, it is wrong - at least at 128 kbps, because you will increase frequency resolution of one MP3 frame, but you will decrease time resolution:

- One MP3 frame is 1152 samples
- Sampled @44.1 kHz, this equals to 26 msec, and freq. resolution is 19.1 Hz

but

- Sampled @32 kHz, time resolution is 36 msec, and freq resolution is 13.8 Hz

However, in the second case, short window time resolution is 12 ms - which is too high, and at some transient passages you might experience high pre-echo, because MP3 does not have tools (algorithms) for reducing pre-echo (like TNS, modified MDCT windows and/or gain control)

Well, in mp3 we have 2 granules per frames, so the situation is not exaclty as you depicted.
But overall, this is the idea: trading frequency resolution against time resolution.

Moreover, due to a design issue, data needs to be lowpassed to be efficiently encoded with mp3.