The tool is eliminating polygon PARTS; that is to say, parts of multipart polygons.
I may be mistaken, but it sounds like you are trying to remove SINGLE part polygons that are under a given size.
Eliminate Polygon Part will get rid of holes below your specified size, but leave any other seperate polygon (that may have been in the hole) in place.
If that is indeed the case, you could select the remaining features (including the overlaps), merge them, then explode them again. That could scramble your attributes, of course...