Fixed!
Please let us know what worked so that others may benefit, thanks!
... perhaps he can explain further ...
I removed the Xing header.
In MP3Diags that option is not available by default, through configuration you'll need to move it from 'Invisible transformations' to 'Visible transformations first.
If I understand correctly, while these headers are necessary for VBR files, they may be absent/removed for CBR files.
(if anyone has different information or experiences, please chip-in)
@NailJ: Be sure to keep your original files stored for a while in case the performed lobotomy has some negative effects. (I don't expect so, but you never know)