Every domain is paid. But if you bought it from an authorized reseller who's authorization is revoked, you're still screwed. Mali is the true owner of all registered domains in its country.
Correct, I also read that the .ml addresses were free, but in hindsight this downtime is a bigger cost to bear than the $10/year or whatever it would cost to properly pay for a domain.
In hindsight, yes. But there was no indiciation ahead of time that this situation would happen or was likely to happen. In fact, there was no more reason to believe a free ccTLD was any more likely than a paid ccTLD to cause a problem. The problem arises because a ccTLD's host country can choose to remove any domain it wants, paid or not. One could argue that using a ccTLD at all was a mistake, but you'd have to look at precedent for ccTLD's country's doing this and see if it happens often or not.