Simple Green
On the lower end of my engine work I use the gel hand cleaner from Pep-Boys and a cheapo nylon brush set from Harbor Freight - with various lengths and bristles. Breaks loose the really heavy stuff, without having to resort to any high pressure water streams and the problems associated with going that way.
Prior to doing any painting I always buy a couple of cans of light gray primer and put a very light coat down to highlight any clean-up imperfections. I know, sounds crazy - but it makes any crust left over stand out like neon. Once you've chipped of any crud it's easy to sand any signs of problems and put another coat of primer on before finish paint.
Works for me.
Mac.