[Suicide Junkie]

Right, that's the whole problem.
Odds are you saved the game after sending the political message in which war happened. Which causes the politics to go out of synch.

If you change the AI to be human-controlled, I betcha 1000 minerals that they see a Trade or better treaty with you.
They might even be getting resupplied at your mined planet if you had military alliance beforehand.

As I said, if you can convince them to sign a treaty, you can then declare war again the turn afterwards, and it will work (if you don't save after sending!)
Or, you can take over their empire for a turn, and send a declaration of war to resynch.