Double check that your board is the 3V 8 Mhz Pro Mini and be completely sure that it's selected in the IDE boards menu. I have had this exact same issue before and the wrong IDE choice is what causes the baud mismatch.
Moderators: I previously posted a reply to this issue on a very old post before seeing this one. My bad, sorry. I'm getting the hang of this but as a slow learner I suppose. Sorry.
You probably got a 3.3v@8MHz version instead of 5v@16MHz. Is it an official board or a cheap clone? The people selling cheap clones definitely get them mixed up sometimes - since the cheap clone manufacturers never mark the boards as 3.3v or 5v (I often see boxes on the back on the silkscreen, meant to be marked after manufacture, but I have never seen them filled in! And I have bought, uhm, a lot of different pro mini and nano clones)
So, before I suggest something more, please clarify what board you have. That is, where did you buy it - specifically. If you can attach a photo of the top and bottom of the board, that may help. Otherwise, see if there is a check-mark or other marking on the bottom that indicates the voltage.
If this info doesn't give a solution, there are ways to measure some things to determine the model but for now, keep it simple.
Regarding your facts about the wide supply voltage range, this is because whether you have the 3V or the 5V model, RAW supply voltage (sometimes marked BAT) can be anywhere in the wider range and the board has a voltage regulator that precisely outputs either 3.3v or 5v depending on which model you have. As long as we're to this detail, you can determine which board you have by simply connecting a power supply of at least 6 volts to the RAW or BAT terminal and then measure the voltage OUTPUT of the Vcc pin of the Pro Mini. The voltage reading will match the board that you have, i.e., 3V/8MHZ or 5V/16MHz.