Also, does Google do phone interviews for hiring anyone other than interns?
Yes.
If you're part of the interview team, and they are in another country. The interview team could be spread all over, but usually, it's only one or two people who do the phone interview. However, in that case, they're usually in the conference room at a google facility, so you have full on video conference capability, even if it's a two person room. Usually they use a 4 person or larger room so that you have a whiteboard on the wall with a camera pointed at it, and can switch viewpoint and see the whiteboard.
If you can't travel, they'll also do them, and if you passed the phone screen, but they want a technical opinion before they bring someone on site (mean fly them in), and they happen to be pretty far from any Google office.
I don't think the above discloses anything that should not be IOTTMCO.
I thought the phone screening and was a relatively easy hoop to jump through, with candidates that don't fail being pulled in for a real interview. Oh, and doesn't Google still have a corporate policy of never giving feedback on interviews or reasons for rejection, for fear of lawsuits?
The phone interviews I've given were all real interviews, not just phone screens. On the other hand, being in a position where the recruiters tend to like you, and the hiring committee tends to trust your opinion, you see more of those than most people.
The corporate policy exists to prevent one bad interview, due to bad chemistry, a hangover, or whatever excuse for having an off day the interviewer happened to have, from damaging the interview process overall. Google employees can screw up too, and if they do, it shouldn't cost Google a good candidate, and it shouldn't cost the interviewee their confidence in the remaining interviewers, where they might prove to be incredible people to hire.
A lot of passing an interview process has to do with confidence, and if you shoot someone's confidence in the head, even if you don't think they'd be a good fit, then (a) you're an incredibly bad interviewer, and should either redo the training or be barred from doing future interviews; that's OK: not everyone can be great at everything!, or (b) you've made a mistake, and you probably need to immediately tell the recruiter managing the interviews, and the next interviewer on the way in, at a minimum, and then disqualify your feedback to the hiring committee, and tell them why, so they can look at the remaining interviews in that light. The absolutely worst thing you could do is make a mistake and not tell anyone about it. They're not rewarded, but unless they are habitual, neither do they cost you; you tend to get +1 integrity points (that's not a real thing).
The whole anecdotes smells a bit off to me...
Yup. Me too.