Madagascar, Caribbean, and Greenland are the three that really challenge me. They each have no land borders and only a sea port, so if they shut down the sea port before you've infected, you've basically lost the game unless you pull some heroics out of your butt. Of the three, Greenland is the hardest, I think because it is so seldom visited, and only from a very few places. Also, since it is sparsely populated and has few transmission vectors, the disease spreads very slowly. Finally, the Greenlanders seem more willing than most to exterminate the infected people once the disease gets to about 100 or so. Starting the game in Russia and buying water-transmission early will help you get a jump-start on Greenland, but watch that you don't end up in the same situation with regard to Madagascar or Caribbean.
I kind of know what you're talking about, but each disease requires a slightly different strategy. I'm still having trouble beating Bio Weapon level on Brutal, although I've come close a few times. The strategy of "keep your head down so they don't start working on the cure and then go super-lethal" is hard to implement when Bio Weapon kills people off without evolving any symptoms.