Even the first of those two doesn't really appear to be that strict a requirement. The point in the episode "Attached" was that on Kesprytt III, one part of the planet, under the so-called Kes government, would join the Federation while the other, under Prytt government, would not. It would suffice for the joining part
to have a single government, then - the Kes would not be required to conquer the entire planet first. Had this taken place, it would have been a first, but it still could have happened.
So basically it just boils down to a culture being "contactable". If you can make First Contact with 'em, you can also invite 'em in.