Do some diagnostics at least for the temperature sensors. A cheap ODBII adapter is suitable for that, but you can do far better analysis with an OP-COM. Replacing parts is pointless without a direct feedback about the effect of the change.
Anyway, are you sure about over fuelling? Build-ups can be caused by many other factors either.