[azernik]

Palestinian passports are recognized in lots of places. And assorted governments in exile with control over zero territory issued widely-recognized passports throughout WWII.

States recognize whatever passports they want to; usually this is based on there being people with those passports that the state would like to be able to identify and authorize to enter, and usually you have to control territory to do that.