They're not invincible, and some people have managed to beat three or four vicious at once. The only difference between vicious/cruel and unfair is resource cheat; they get a lot more.
Of course, there are some known defensive and offensive combos the AI simply cannot beat, so if you can survive long enough to field them the difficulty stops mattering because the AI cannot beat you no matter how many resources they have. The trick is surviving that early game, which is usually a matter of distraction tactics and moving quickly to secure the key choke points before the AI's arrival.
The AI notorious for its slow deployment speed, and its resource cheat helps relatively little in this regard, so it's still easy to colonize two to three times faster than the vicious AI.
