The boot order change is likely a reflection of intermittent-detection. Sometimes your machine is picking up the HDD, sometimes it is not. When it is not, the boot order is switched, likely placing the HDD at the bottom of the boot order. Boot order really isn't important, its the drop out of the HDD. This is either a cable to the HDD, or a drive about to die. You can always pull out the drive and stick it in another machine to see if it boots. Alternatively, put a copy of linux on a USB drive, run it for a bit, and see if everything else generally works. There are too many variables, you need to isolate the root cause. Virus scanners, MBR's and the like are not likely to help you.
Newer machines may not have HDD's in the traditional sense that it looks like a harddrive, sometimes they are just small cards/PCB's now.