More questions than answers..
• What have you tried thus far?
• When you ran scans (other than McAfee) to check for malware did they find anything?
- If you haven't done so already, you may have to jump through some of those hoops you referred to. It's the only way you're going to rule out malware as the cause.
• Do you have additional security software installed on the system? (Or remnants of "days past"?)
• Are there any error messages or alerts when the firewall shuts down?
• Are you experiencing any other "issues" with your OS?
• Did you run the Virtual Technician?
• Did you try uninstalling McAfee, followed by their MCPR tool? And then tried installing it again to see if it makes a difference?
By the way, I did find a thread at the McAfee forum where a member resolved their firewall issue. It doesn't mean it will resolve yours, but have a look here anyway. Make sure to read the second page.