When white walls get kind of filthy due to smoking or dirty finger here and there, is the only solution to paint over? Or is there any product that could clean them once in a year or so to keep them fresh looking?
The answer is "clean walls AND paint," if you're going to paint at all. Even if you do decide to paint over a stain you can't remove, you still need to clean the wall to make sure the paint adheres properly.
I use TSP to wipe down the walls or surfaces prior to repainting. It cuts the level of surface gloss, really cuts through grease, and gives you a nice clean surface for new paint - all with a quick wipe down and minimal scrubbing.
Depends on the quality of the paint and the sheen really. Generally speaking the closer to a gloss finish the easier it is to clean. Glossy surfaces are going to be less porous than flat surfaces, therefore easier to clean.
If you decide to paint, like other answers have mentioned, always sand and clean the walls before hand. Prep work is very important for paint adhesion.
A simple mixture of vinegar and water is a good cleaning agent for paint as it is less corrosive than a chemical cleaning agent.