You said only polyhedra with holes don't follow euler's formula, this seems to be true by the definition that you are using. But I think many people call some nonconvex polyhedra like the ones you eliminated... well, like I said "nonconvex polyhedra". In which case their Euler characteristic would not be 2.
But that is not too important, I thought it might be instructive for some people to see an example of something that some people call a polyhedron (but it wouldn't be under your definition) but to a non mathematicion, might seem like a perfectly reasonable solid to be called such. So if you take two cubes, one smaller than the other, joined at a face so that the smaller cube is not touching any of the bigger cubes big edges. This has Euler Characteristic 3 instead of 2. Great article, just thought people might be interested to know about what restricting faces to being polygons leas you to. Of course there are some nonconvex polyhedra with polygonal sides that do have euler characteristic that isn't 2, but these don't satisfy you condtion about having parts seperated by a 1 manifold. Great article!