I had the same issue (space monster variant). Better AI and higher difficulties increase the chance to get a problem.

Maybe the quest could be changed like this: clear our sector of all pirates/space monsters with a check that X objects are left.
Player could be lucky that an AI assists but this is far better than an unsolvable quest.

There is also an issue of all "pirate types" being included for each quest: e.g., for "kill the pirates" I get credit for killing monsters/guardians, but must kill one of the proper type to finish the quest.  So I can kill 6 pirates, and one monster, for a "7 monster quest" so long as the monster is the last one.

(edit) to be clear, I can kill 2.4 gigabytes of pirates, and one monster, and that is a way to succeed in the monster quest.  The last ship killed is the only ship in the quest that cares which "pirate type" that it is.

This is an exploit sort of bug, and of the sort that annoy me.  No matter how much I might try to get around not killing pirates until getting 7 monsters, I have to kill the pirates blockading my world.  I'm forced into the exploit.