Hi Azzy,
you could be right. Maybe arduino is still expecting to find a bootloader...
I just picked a new Pro Mini from my drawer. It comes from Sparkfun with their "big" 2K bootloader.
After, I simply uploaded the sketch by using the following configuration:

So I didn't preventively burned the bootloader.
I never burned a boot-loader before, can you post a link to an example?
More difficult for me is how I can understand if a board definition set the fuses or not. What I should check/search? In what configuration file?