It seems that there is some junk between the tag and the first valid MP3 frame. foobar2000 and Winamp probably display the correct information because they decode more than one frame.
Florian, how exactly are you looking for frame headers? Are you evaluating the first frame that starts with 0xFF 0xF_? A good approach would be doing something like this:
Search for a sync word starting with 0xFF 0xF_ and assume it's a good frame.
Calculate the frame size and store result in x and move the file pointer x bytes forward.
3a. If you found a valid frame there, it means that the first frame was indeed valid.
3b. If you didn't find a valid frame there, the first frame found was a false positive and you should search for another frame.
My post states why. There is junk between the ID3 tag and the first valid frame of the MP3 bitstream. That junk looks a bit like a MPEG frame since it has the same sync word like a MPEG frame header.
The quality of the file is not affected since foobar2000 will only remove tags and any non-MP3 data. It alters the MP3 audio frames in no way.