There's a few scripts out there that will rebuild a mesh from scratch to avoid these issues. It's been so long since I've needed one, I'm never sure if it's my workflow or the software getting better. Hypergraph with Heirarchy view is helpful in troubleshooting a mesh, sometimes you'll still have crazy inputs left over…
Does it only happen when you use specific tools? (The interactive split tool for instance is VERY unstable in 2012 so I always use the old one). You could try look for scripts with similar functions as those tools, they are often better and more versatile than Mayas built in tools. Not sure it would make a difference…