It sounds like a similar problem to one that plagued us for a while and unfortunately we didn't come up with a simple solution. We found that sometimes, if we mirrored poly geometry and then combined it with unmirrored geometry it would, very occasionally, screw up the vertex normals so the smooth shading across the edges and faces would be inverted and the faces would just look black... no amount of vertex normal unlocking or fixing would solve it and we ended up having to go through a tedious and complex export and import process to destroy all the normal info in the object. It was almost like Maya was holding some deep internal normal info for certain vertices that we just couldn't get at...
Once we improved our model making processes and model "purging" tools though we practically stopped getting the problem.
Since that episode I actually wrote a MEL script to rebuild (from scratch) any selected faces of a model but, while it works, I never made it reproduce the original edge smoothing or UV mapping coords so it's probably not that much use to you. I should probably update that script... one day.
:nathaN
