the problem is that google authenticator stores the seed in the phone(and the server) so if you lose it basically you lose the server too, right?
http://code.google.com/p/google-authenticator/source/browse/...
If you lose your phone and your scratch codes, you've only lost access via SSH. So it's an inconvenience, but one you can overcome with the right setup.
Yes, if you lose either factor, you can't access the server. This is why with Google Authenticator you also get a one time pad with emergency codes. However, I don't know how well this would work with two-factor SSH... you'd need a separate one time pad for each server. And I'm not sure how the Google PAM module handles emergency codes.