I remember that the poly count used to be 1 million polygons (triangles).... Has that changed to half? Or 500,000?
Are you sure you are looking at polygons and not vertices? I've spent more time than I like to admit trying to figure out why models won't be accepted because of this.