I think this could be related to your Windows user privileges. I run with a high level of privileges, and I installed Firefox as myself (not as administrator). Maybe that's why I never need to restart Windows to update Firefox? Hopefully another volunteer more experienced at troubleshooting permission issues can sort it out for you.

By the way, do you use the "background service" method of updating? These articles describes that option:

• What is the Mozilla Maintenance Service?
• Advanced panel - Accessibility, browsing, network, updates, and other advanced settings in Firefox (see Updates section)

Also make sure that your security software isn't blocking access to files in the Firefox program folder preventing Firefox from updating files properly.