I agree except for the sponge part. A lot of sponges that you buy at the corner grocery, especially the scrubby kind, are treated with chemicals to keep them from molding. These chemicals are bad for your fish.
Here's something I would add: If it's durable, take it to the local "do it yourself" carwash and powerspray it (no soap). This method will take off years of build-up and saves you the cost of a powersprayer if you don't already have one. I DON'T recommend this for glass tanks, but it works great for sturdy plastic, rocks, etc. Another great use for this is contaminated gravel. Put the gravel in a large laundry basket (the kind with with a lot of large holes), lined with some old towels. You can spray the heck out of the gravel, draining all of the yucky stuff out onto the towels. If you want to be really thorough, bring a second laundry basket/towel set and dump the gravel into this clean setup for a second rinse.
I'd also suggest that once you get everything set up again, before you add any livestock, run a diatom filter for a couple of days to get rid of any trace of nastiness that might be left.