Todd’s right, the Mesh cleanup with select matching polygons is your friend here. Some other tricks that I find useful:

1, Turn on Display Border Edges in the polygons display menu as if there are adjacent polygons with reversed normals, then they can show up a border edge.
2, Turn on display face normals and check that the normals are correct. If you’ve got them in both directions then it’s a sure sign of problem 1 above.

The most difficult one type of non-manifold to deal with can be number 1 in Todds list. Make a duplicate of your model before you start this!
Use the Mesh cleanup with non-manifold (as described) and select the polygons. Then, sometimes you can just hit delete and get rid of all of the problem polygons, sometimes you may need to do this by hand.
What you can then end up with is non-uniform normals (faces pointing the wrong way), so try out using ‘normals - conform’.
Finally, you may need to select all of the vertices and merge them. At this stage, if everything’s gone OK, all of the border edges within your model (except the border edges themselves) should have gone.

The above few tricks are normally enough to sort almost all problems. If there’s a small number of really troublesome faces, then sometimes it’s easiest to delete them, fill the hole and then split polygon to put back the edges. Obviously, this is only going to work on a few polys.

I’ve never really worked out what causes the ‘whole model made out of non-manifold polys’ problem. I know that the extrude tool, if selected then not extruded will leave faces that you can’t see. If you then merge the verts, then you will start building up problems. Aside from that, I would love to know what causes them so that I can stop getting them myself!

Cheers,
Ian