SMS verification on demand only
Something Hotmail service is calling as "Disposable login". When you're on a public computer, you have to enter correct e-mail and the single use password will be sent to your phone via SMS. You can then log in using this one time use password. When session expires or you sign out, the same password cannot be used again. However at home it won't be bothering you with double verification because it's in most cases unnecessary and just makes it annoying to use. So in this case Hotmail's solution is much more flexible and user friendly while also keeping security at an appropriate level.
Critical account settings modification verification via SMS
What's more important is the account main settings lockdown. This means personal info, login password, account recovery features and so on should only be visible after verification via SMS and also be modifiable after SMS verification.
This way you can't just walk into an ongoing session and change or view critical login information.
Also this would pretty much eradicate any possibility of hijacking accounts.
What is the usual scenario when you get an account breach? The attacker quickly changes password and recovery settings. Even SMS settings that are otherwise available in most services can easily be modified just like that. When all this is done, the original user is pretty much fucked. It's a design failure to begin with.
But in my scenario, only way to hijack account would be to also steal your phone. There is no other way in doing it. Why? Here is a "live" scenario...
Attacker somehow manages to get inside your account and read your mails. As much as it sounds bad, it's even worse when you get locked outside of your own account. But in a SMS secured account settings, attacker will be able to read your mails indeed, but he won't be able to change your login password or recovery settings unless he can get the verification code from your phone.
So in this case he'll be able to read your mails but when he'll want to change the password, verification SMS will be sent to your phone. And without it he can't even access (view) critical account settings, let alone change them. And since SMS verification settings (phone number) is locked down with this feature he can't bypass SMS verification either. Since GMail offers IP logging you can rather quickly spot any unauthorized access to your account and change the password. Some data might leak from your e-mails but it's nowhere near as bad as losing control over your account and losing ALL your e-mails.
Downside of my SMS verification lockdown
Now the base idea is very secure and is pretty much impossible to bypass. But there is also a bad side of it. If you change your phone number before first changing it inside your account will result in locking yourself out. So in this case you have to be sure to first change phone number inside your account. Another problem is also a stolen or lost phone. But this is just a temporary problem. In such case you have to quickly contact your mobile service provider and disable the original SIM card remotely, making it useless (even pre-pay service users can do this by proving phone number ownership with the credit card sized frame to which SIM card was attached when they bought it). Then you have to request a new SIM card with the same phone number (but different PUK obviously). This way you regain control over your account access.
I hope someone from Google is reading this and that we can see this kind of level of security in their service very soon and that other providers will follow as well. Sure we have to give away phone number to "evil" Google that's collecting all our data, but with it, security of our accounts would skyrocket as well.