Interesting, in my current game I too had several Destroy 5 ships/structures but after that was completed I've gotten more missions as usual and it seems to be working fine in my game.
As for the send envoy spam, I usually just would have one envoy short of their total number of planets and whenever they gave me the mission I would just jump one of my envoys from one nearby planet to the other ad naseum. They still gave me some give credits/metal/crystal missions occasionally though. I just wish they were more responsive when I send them a send envoy mission.