Looking beyond Gmail, Friendster has been in Beta since the beginning of time, but they have well over 6 million users now. Technorati was in beta for a quite a while, but recently dropped that label just before being launched into the media spotlight by CNN and the DNC.
I suspect that if anyone even notices the Beta label anymore, they don't think twice about it. If the company was willing to put their service in front of millions of users, how likely is it that they're not reasonably confident that it's "almost there" in terms of usability and stability.
It's not like the old days when software beta programs required you to apply and then demanded regular feedback during the process. I think that in many (most?) cases, these on-line "open" betas are really just an excuse for launching services before they're ready.