Why should I replace the starter every time I replace a fluorescent tube?
Modern electronic ballast technology (T8, T5) doesn't use starters. I associate starters with old, inefficient magnetic ballast installations. I haven't had to replace a starter in years because they have not been used in any of the newer buildings I've worked in.

My preference would be to convert any T12 installation with magnetic ballast and starter to T8 tubes with electronic ballast. The tubes run brighter and consume less energy, and since the ballasts use far less copper, they can be obtained in the $10-18 range.

Flickering lamps on magnetic ballasts can overheat the ballast, so it's pretty cheap insurance to replace the starter and both lamps so you don't burn out a heavy copper-wound magnetic ballast which in the day was quite expensive to replace. 

Another reason is that failing starters can cause premature tube failure which kind of negates the reason for replacing the tubes. Filaments in the ends of the tubes stay on too long causing excess sputtering which turns the tube end black from the metal deposit and early filament burnout causing the tube to not light. Starters have two failure modes, the bimetal gets weak and delays opening keeping the filaments on too long, the contacts burn and the filaments don't light up during the starting phase.