If they hold key provinces they can't be annexed, so random province of yours doesn't matter, but if it has vp in it then you need to conquer it back.
If I remember right that also means key provinces they might occupy from a third nation. So if you're US and are fighting against Japan, who is occupying parts of China, then you need to conquer those Japanese held Chinese provinces as well before annexation is possible.