I'm sure someone is probably working on this, but what about a service that generates a one off seed for the second stage of auth, married with either a desktop or smartphone app for generating it for the user. Lose your phone/laptop/PC simply cancel it remotely so it stops generating, same as you would if you lost your bank card.
I'm sure I'm missing something, but I'm not sure what.
EDIT: I'll let the post stand but I need to read more clearly, I thought Google Authenticator was purely for Google services.
You can actually authenticate against the GA product from any system - hook it into PAM for sshd access, use it for another factor in OpenVPN, or even just wire it into Apache:
I'm sure I'm missing something, but I'm not sure what.
EDIT: I'll let the post stand but I need to read more clearly, I thought Google Authenticator was purely for Google services.