From what I understand--
The "lossy" part of MP3 is that the encoder decides to throw away frequency bands to reduce the information size.
This is more than just choosing a bitrate and being done with it - different encoders treat different bands as important or unimportant, attempting to make a smaller sized file still sound better.