The problem is that the ship only checks fuel status when going from Order A to Order B, not in the middle of performing Order A.
So, for example, your survey ships has 100% fuel at Earth. She then checks that the nearest body in need of survey is Pluto. Off she goes. The conditional logic doesn't check whether the ship has enough fuel to even reach Pluto. This is why I always use the "Survey next body" instead of the "survey next 5 bodies", as the former at least allows the conditional logic to check fuel status more often.
Always make sure that your survey ships have enough fuel to go at least over 10 billion kilometres, preferably 20 billion.