Adding an "STL Check" modifier after the 'Editable Poly' will fix the problem. You can then collapse it as well, this will turn the Editable Poly into a Editable Mesh but you can convert it to Editable Poly again with a Edit Poly modifier. Modifier madness, hehe :P
Yeah, 3Ds Max is weird like that. Sometimes you have to convert your object to Editable Mesh and back to Editable Poly (copy/paste your modifiers if needed), usually solves any of these smoothing issues. I also encountered them when using the Cut tool, or in the middle edges when applying Symmetry or when capping a border…