The "space is big" vs "not being able to complete missions" is one of those realism vs gameplay deals, which I'd prefer leant more on the side of gameplay.
Deliberately avoiding missions because they contain certain words/phrases which mean you have an incredibly low chance of finding the target feels "gamey", like you're being offered a choice which you know has a significant chance of punishing you. Once you're aware of this, why would you ever choose to do that?
Maybe some of the hints could be improved a little.
As noted, you can't really really say something is "near planet x" as that removes any need for searching.
But you could say that something is "in the orbital region of planet x". That would give a decent sized area to search and the player (probably) wouldn't find it right away, but it's not so large that it's offputting.
This would have the same mission effect as the object being in an asteroid belt. You need to search the edge of a circle, which is bigger the further away from the star it is, but you know exactly where you need to look and its a limited area.
A similar thing could be done for the outskirts mission targets.
Just arbitrarily decree that all system maps in-sector use NSEW as a cartography convention for ease of understanding, and then have the mission hint point the player into a quadrant or segment depending on how you want to divide up the map.
The mission effect here is still broadly the same as it is now, but you've narrowed the search area down by a significant amount.