With the exception of finding new hidden systems, as Darian mentioned (and which can be literally anywhere inside a sector), you can't find asteroids or planets in deep space. This is because "deep space" in the Combine is, in programming terms, the absence of a system. We don't have any method to implement "rogue planetoids", so every one has to be inside of a defined system.
Yea, as said above. It's simply a contradiction in terms. You can go to what you think is a deep space coord and find a previously unfound system containing planets or asteroids. Then it is no longer deep space as you have revealed the system.