You definitely don't have to be commissioned to get new ships, even good ships. It's true that you typically find the best ships in the military markets, but it's far from necessary to be commissioned to get the best ships - it's not unheard of to find even capital-class ships in the open and black markets. Heck, I got my Odyssey off the open market, and I've seen Conquests, Legions, Astrals, and Onslaughts just in the same places. Look for planets that have Orbital Works industries, and military planets (even if you're not commissioned there still tends to be some juicy stuff on their open and black markets).
Don't be afraid to arouse suspicion buying black market ships either - when you buy a ship off the black market, even with the transponder on, it doesn't cause a change in the market, so you won't get a reputation hit. As long as you're not carrying anything illegal, the resulting security scan won't matter either.