| While a simple1 "majority" is more than 50% of any total, a "vast majority" is harder to define. The phrase "vast majority" is most often used to exaggerate the size, relevance, or importance of some statistic.
For example, one might say, "Although George W. Bush received the winning number of electoral college votes in the 2000 U.S. Presidential election, the 'vast majority' of voters cast their votes for Al Gore.2 So Al Gore is the legitimate winner."
But even if the majority of voters in the U.S. did cast their votes for Al Gore during the 2000 U.S. elections, that majority could hardly be called "vast". It was very close. And the fact is in any case irrelevant to the legitimacy of Bush's election.3
On the other hand, if, by "vast," one means "large," and since "large" is a term which is necessarily relative, saying "vast majority" could simply mean that the majority is larger than the minority. But that's always true of majorities, by definition. So in this second reading of "vast majority," the term would merely be redundant.
And finally, the third possibility is that a "vast majority" is a majority which is "vast" compared to other majorities. In this meaning, it isn't clear where exactly to draw the line -- maybe at 80%? -- but it really isn't a useful descriptor. The only useful descriptor is data.
To avoid ambiguity and the appearance of exaggeration or stupidity, the phrase "vast majority" should be altogether avoided, and instead, say simply, "majority" (which does have a clear meaning), or "X % majority", identifying the exact percent-majority that you consider to be "vast".
1. As compared with, for example, an "absolute majority," which requires one candidate to receive more than 50% of ALL eligible voters, whether they voted or not, and a "super majority," in which the threshold is two-thirds. The most common meaning of "majority" is "simple majority." Thanks to Cletus the Foetus for this reminder.
2. The fact may be, as Jurph asserts, that neither Bush nor Gore received a majority of votes cast across the United States. Rather, says Jurph, Gore received a plurality of votes. But of course, we'll never know which candidates received what number of votes, because the precise number of votes was never agreed upon (since the Florida recounts were aborted), and many states didn't even initiate recounts despite having very close results. Many voters believe that if all of the votes had been counted accurately, Gore would have prevailed with a majority.
3. That is, IMHO, Bush's presidency is potentially illegitimate for an entirely different reason, namely, the failure of all Supreme Court Justices to exclude themselves from the Florida electoral matter because of personal (political) interest in the outcome. | 
