That's a lot of work. Sometimes manual work is required but if you can accept some minor vertice moves an automated process can do a lot. What attributes did you lose when you used the Integrate or Eliminate tools?
Ideally, there would be a batch topology fix for gaps and overlaps but I don't know of any. Maybe I missed that and someone can point us to it.
I like to use ETGeowizard's clean and eliminate tools when I'm given a topologically messy polygon set, but these aren't the free tools. Since you have ArcInfo you could use the Feature to Line and Point tools, then Feature to Polygon using the points for attributes. It would fill in all the gaps and the overlaps would become their own polygons, both of which would lack attributes. (Well, it is possible a point would get into a sliver rather than the "home" polygon so you would have to check for that.) Then run an Eliminate, but check the results; you may have to vary the tolerance to get enough eliminated without unacceptable vertice movement.
