Are you getting your e85 from a station that sells premix, or a blender pump? (one that mixes ethanol with gas from the main station tanks)? What you might be encountering is due to the fact that premixed e85 is often mixed using very low grade gasoline (85 octane or lower - the ethanol largely makes up for it). It's probably sourced from the small amount of gas that is directly extracted from low grade crude oil or natural gas production, as opposed to the majority of gasoline which is processed in some way or another to obtain higher octane mixtures. A number of different processes are used - cracking, alkylation, reforming, etc which all produce slightly different mixtures that will pass the same "octane" rating tests.
What we think of as "gasoline" is really an extremely variable mix of several dozen different liquid hydrocarbons of different types that can pass the combustion and octane tests which allow it to be sold at the pump. (LPG is a similar product). The only real common feature of this mix is that the hydrocarbons all boil around the same (gasoline) temperature when separated from components with higher or lower boiling temperatures during distillation. Before it goes to the pump, it is modified via additives (detergents, ethanol, MTBE, etc) in order to bring it up to various standards.
The feedstock (crude oil) that is used also produces very different mixtures depending on where it came from. "light sweet crude" tends to produce more gasoline with higher octane and light hydrocarbons, where "heavy crude" and "tar sands crude" tend to produce heavier hydrocarbons, and the gasoline that results can contain a lot of heavier tars and waxes. The gasoline from the latter tends to be anywhere from 60-80 octane, and is usually processed in some way to produce consumer gasoline.
E85 blends can be made using cheaper, less processed gasoline when it is available, which leads to many of the problems you are encountering. This is often done to offset the high cost of ethanol, which is not only fairly expensive to produce, but cannot be transported via pipelines because it attracts water, which then contaminates other petroleum products that are also transported through the same pipeline (this is done by inserting a "plug" in between batches of fuel, which keeps the fuels separated). In some cases, lower grades of gasoline are actually required in order to allow the fuel to vaporize more easily, since ethanol does not, especially in colder parts of the country. Recall that the opposite is true - higher octane gasoline vaporizes and burns less easily.
Compounding the problem is that many of the normal gasoline detergents (that prevent the tar buildup that you are seeing) are not compatible with ethanol, and also in ethanol blends, only the gasoline portion contains the EPA required minimum additive levels. (A sidenote - the main difference between cheap gas stations and "top tier" stations that tend to be more expensive is not that the gasoline itself is any different, but that the levels of additives are higher, mainly detergents)
It's such a problem that professional race teams that have switched to e85 have had to source their own blends from manufacturers, which can be blended from a combination of high grade (low water content) ethanol mixed with race gas - the result is much higher quality than the E85 we can get at the pump.
If you have a lot of time, here's a DoE primer on Ethanol fuels:
Ethanol
A couple of recommendations if you are having this problem with E85:
1) If your car is still dual-tune, run a tank of 100% gasoline from a "Top Tier" station every now and then (Chevron is my preferred, but there are several. Some independent stations are also certified:
Top Tier Stations - You'll probably want premium, but detergent content is unrelated to octane rating)
2) Find a bottle of E85 compatible detergent additive - Chevron's "Techron" is available at many auto parts stores in a bottle. "Seafoam" makes a gas tank additive that is E85 compatible - not to be confused with the popular "spray" product.
