Reliable cleaning processes are an absolute prerequisite to ensure the production of safe foods. In particular, the cleaning of heat exchangers is a crucial process step since temperature induces the formation of strongly bound food-borne deposits. Aiming on relationships between soil-specific physicochemical properties and cleaning behavior, four native starches of different botanical origin (maize, waxy maize, potato, wheat) were selected for plane channel flow (similar to the flow regime in plate heat exchangers) and falling film cleaning experiments. In addition, their chemical composition and swelling behavior was analyzed. Different cleaning mechanisms could be observed, whereby diffusive dissolution was identified as dominant cleaning mechanism for most starch deposits in both cleaning experiment setups. The cleaning of such soils is characterized by an initial reptation time, where the cleaning fluid penetrates the soil and no cleaning occurs, followed by a period with constant cleaning rate. Since these cleaning parameters where overlapped by swelling-induced processes, a correction model was used to identify the unaffected cleaning progress. The cleaning and swelling-induced parameters were influenced by the origin of the starch as well as by temperature and sodium hydroxide concentration of the cleaning fluid. Multivariate statistics was helpful to unravel interrelationships and interdependencies between results of cleaning experiments, and compositional and physicochemical properties.