NINJ4R4BBID: This mess is mostly due to Microsoft(s) incompetence!!!
I also had this problem (on Windows 10 x64) and didn't even know at first i had it, only when i tried to play the game on my second PC that i noticed the difference in performance.
Turns out Microsoft has two different versions (at least) of XNA Framework Redistributable 4.0!!!
Microsoft XNA Framework Redistributable 4.0 (GOG(s) __redist contains this and it causes performance issues for some people)
Version: 4.0
File Name: xnafx40_redist.msi
Date Published: 9/16/2010
File Size: 6.7 MB
File name: xnafx40_redist.msi
Authors: Microsoft Corporation
Revision number: {DC84B1CC-8305-4856-B0CB-96DBD0DE375A}
Content created: 23.08.2010 23:15
Microsoft XNA Framework Redistributable 4.0 Refresh (Steam(s) _CommonRedist contains this and it works as a fix for most of the people that have performance problems)
Version: 4.0 Refresh
File Name: xnafx40_redist.msi
Date Published: 10/6/2011
File Size: 6.7 MB
Authors: Microsoft Corporation
Revision number: {D9535E20-EEE2-416F-8CC0-4335088F4B6D}
Content created: 02.09.2011 03:09
So everyone who had "4.0 Refresh" version of XNA runtime already on their system had no problems, but people without XNA runtime on their systems who installed GOG version and accompanied runtimes could (and have) experience performance problems.
P.S. Also fun exercise... guess which one of the two you will find on a simple "XNA Framework Redistributable 4.0!" google search!? :)
Looks like you've figured it out.
Doing the steps in the OP didn't work for me. Simply uninstalling the XNA framework and installing the refresh version did the trick though. I did restart between uninstalling and installing each version but that may be unnecessary.