Buf
I think your problem was due to a floppy disk left in a floppy drive.

When you changed the boot order, the floppy disk drive was ignored. Therefore, you did not see the error message. Check your floppy drive for a diskette which you may have forgotten about. By the way, if you find a diskette in a drive, (or possibly a thumb drive inserted), the floppy was probably formatted with an older version of MS-DOS such as version 3.3

This explains why the reformat of your hard drive did not work to remove the message.
If this was the problem, there is no need to worry about changing the boot order in the future .....as long as that diskette or thumb drive is not inserted!