I think that this is not entirely true - Vienna has to be defined as both a state and a county, else the counties in the other Austrian states would face the same problem (not being able to exist because the "county" space is occupied by the states already), yet they do have their shape data. Vienna, on the other hand, is a bit of a mix. It is both a state and a county in some ways, but the subdivisions of the city work just like they were counties of another Austrian federal state. They have their own local government, census, etc. The only thing they don't have is own car number plates.
Thanks for providing the link to the checker! I think there is at least one challenge like that here.