Start with a parasite anywhere with both an airport and shipyard, sell your starting symptom and purchase moisture and drug resistances. Wait for a blessing from RNGeesus and you will eventually land in every country long before ports and borders close. This strategy has rarely failed me, and then usually because of Peru.
Try for a Mexico or Brazil start for best results. The bonus heat resistance seems to help it hit Madagascar faster, but that may be a coincidence.
Honestly the Madagascar start does more harm than good, because if your infected population gets too high there, EVERY ship will be a plague ship and your disease spreads too fast and people panic. You'll lose countries that way.