Oh, actually, I believe Groin’s proposal (if tuned appropriately) mostly takes care of the points anoek brings up there:
You can set up a “beginner room” where new accounts (if they self-identify as beginners) can play their first, say, 10 to 20 games. Then they can get introduced in the bigger pool of established players with a provisional tentative beginner rating based on their performance in the room (like, between 20k and “30k”, for example).
Because of this:
It really seems that we don’t have an unmanageable influx of newcomers, much less beginner newcomers.
While on one side this is a shortcoming of Groin’s proposal, because it means beginners can’t always play other beginners, this actually means we probably have the resources to monitor most, if not all, games going on in that room, and recognize the sandbaggers when they show up.
(We could implement this idea incrementally to make sure we have the resources: first have the beginners play only a few games there, and increase periodically to see how many we can handle)
Or in other words, if we have volunteer (hopefully trusted) teachers, and mods when they can, hang out in those rooms too, they can recognize the fake beginners, and hopefully even explain what happened to the real beginners that have been sandbagged.
If there’s only one beginner, they play their first games with a volunteer teacher.
I believe this also solves the other little problem I was worried about, that beginners playing unsupervised might be rude to each other.
Hopefully, this means the sandbaggers will be discouraged by how much of a pain it is to pretend to be a beginner while being monitored for so many games, and with time they might be a negligible phenomenon.
Wanting to nitpick, there is still a potential problem: TPK sandbagging might become a more pronounced phenomenon, and it will be difficult even for teachers and mods to recognize them. But hopefully in that case the experience won’t be particularly traumatic (for the reasons brought up by @meowkorkor in the bullet list above).
Now, I guess I should sugar-coat this as much as I can, but I can’t resist: one objection I wouldn’t like to hear is “but this could muddy up the statistics”. Yes, there are still ways that could happen (although this system imho would contain it a lot more than other proposals). I think it’s been established that the forum community believes it’s worth it to improve the beginner experience.
Other than that, I invite everyone to point out all the flaws they see in this proposal, so we can determine if it’s worth anything or if it can be improved (I imagine it can) 
(I had another idea first, but the above is much better.)
Here’s an idea that might solve, or at least contain, those problems, and it would help a bit with the sandbagger problem too: you can alternate matchmaking based on the self-declared rating and the “normal” rating.
This revolves around the proposal of assigning two ratings, a “median” one and a self-declared one (with limitations*), to newcomers, and declare them “ranked” when these two converge.
Alternating the matchmaking means the true beginners will only meet stronger players half of the time, and sandbaggers will have a comparable (well, about half the) amount of work to do relative to the current system.
*limitations being, it might be bad for the rating (self)assigned to always be the same, as it might lead to skewing and drifting of the rating pool mostly due to dishonest newcomers, so it might be better if the "self-declared rank" was really more of a range, and then the newcomer is assigned a uniformly random rating within that range, or something like that. Also, don't allow people to set their provisional rank as an extreme of the distribution unless they can certify it.