You need to actually look at each fan to make sure it is clean. The best thing to do is to shut your system down remove each fan and clean each blade. You need to check the video card itself most cards have fans though the fans may appear to be clean there can be a ton of lint and dirt on the heat sink of the card itself this is what needs to be cleaned. As for your system most cases have a filter in them as well so even though the fan is clean if the filter is dirty no air gets circulated. And last but not least check the power supply fan and compartment. It is possible that parts of your power supply is shutting down because of over heat. In most cases this means replacing it.
One other thing you can do is to have a can of compressed air you know the ones you use to clean the fans with remove the side of your computer power it up and when you start getting the stutters hold the can of air upside down and spray in different areas CAUTION the can will get very cold so you might want to wear gloves if the system stops stuttering you just found out what is causing it. I would spray the power supply first as I think that is where your problem is
I had a similar problem but in my case i was losing power to some of my USB devices and it turned out that the +5v Power supply was going bad and I had to replace it. If you wind up replacing it consider increasing the wattage as you could be over powering it. Most video cards require a 12v bus and you need at least a 500 watt power supply as you can see by my system specs I now have a 750 watt dedicated modular power supply which means I do not have a ton of connections just the ones I need. Less cables mean better air flow.