The older, Group I (solvent refined) petroleum oils would generate deposit buildup even with very short service intervals. I'm not at all surprised that changing to a high solvency synlube would clean out these deposits, or that it took a long time to remove them all.
The Amsoil flush is very effective in removing light to medium deposits if you follow my slightly revised procedure:
1) change just the oil filter and add the flush to the old oil....
2) allow the engine to warm up at normal idle speed for five minutes, then fast idle the engine in neutral @ 2x the normal idle speed (1500-2000 rpms) for a full 30 minutes. (Easiest way to do this is get a brick or piece of cordwood and ease it up against the gas pedal until you have the right rpms on the tack.)
3) Change the oil/filter again and install the synthetic
Note that it is very possible you have some underlying condition that is causing the engine oil to degrade more quickly. So I'd highly recommend having your oil tested (preferrably by Oil Analyzers Inc), to see what the problem is. The reason I recommend OAI is that they work closely with Amsoil and maintain a database of all their current formulation chemistries. This allows them to more easily tell if you're getting abnormal contamination or if the wear pattern looks funky. OAI also tests Amsoil for oxidation and nitration separately, which in the hands of an experienced materials engineer can add a lot of insight.
TS