This Aspire is their slimline model, but since the OEM versions of the fan/heat sink is labeled Gateway when you google the P/N it may have been developed by Gateway. It is quite a challenge to work in the compact case.
However after pulling the fan off we notice that the back side of the blades are coated with the same (weighty?) nicotine dust that he had cleaned of the front of the fan blades causing the fan to struggle and stop intermittently. There was some back and forth play with blades, too, which made me pessimistic, but we put the fan back on the heatsink and it has run fine for 12 solid hours since.
I'm still curious why the fan (a $5 part) only appears to be sold connected to the heat sink because it would be nice to be able to screw on a new one if necessary. However if required to replace it then it will be good to re-paste the replacement heat sink anyway to check the condition of the paste.