Unless Firefox is having a problem clearing history because of a file lock, the most likely explanation is that Firefox is not shutting down properly. I don't know what kind of Task Manager/Process Viewer you have on your system, but after you quit (menu button > Quit or File > Quit), check whether the firefox.exe processes are terminating normally. This can take some time if there is a lot of shutdown maintenance, but it should complete within 60 seconds.