When you establish a new base you draw the top 4 cards of the probe deck. But what if the system you'd like, has already been drawn but doesn't have imperial loyalty? Are the cards already drawn by the imperial player off limits? What if all 4 cards you drew have imperial occupation? Does the search start over from scratch for the imperial player?

I'd have thought then... "oh dear, nowhere suitable to relocate to this turn"

You draw the top 4 (or 8 cards) and have to pick from those. If they are Imp occupied or Imp loyal, you can't go there. If you choose to move the base, you turn your previous base's probe over to the Imps.

Cards already drawn by the Imps are off limit (not in the probe deck, so you wouldn't draw them).

Cards you don't choose for a base a shuffled and returned to the bottom of the probe deck.

The search effectively starts over, but he's already narrowed down the possibilities by having occupied systems and probe cards in his hand.

If you draw all Imp systems, you can't move and are stuck. You have to wait till the next turn to relocate again.

False leads is a good card to combo with establishing a new base. It gives you some options to fake out the Imp player and may give you more locations you can consider.