The idea that "deep space stations" are rare and exotic stations outside UFP territory has a nice side benefit. After all, the UFP is an expanding entity. What once lay outside its borders may in a few decades or centuries be swallowed by it (say, with Bajor joining the Federation), at which point a deep space station ceases to be.
The upside? Why, it does sound a bit unlikely that there would be only nine deep space stations in the entire history of the UFP or Starfleet. But if a deep space station has got only a limited lifespan before being absorbed by the expanding Federation, then the numbers are constantly being freed up for reuse. Terok Nor could well have been the eleventh DS9 in history...
...And DSK-7 could have gained that extra letter because it was the K'th generation of DS7 stations.
Timo Saloniemi