They should. Could also do what Facebook (optionally) does: require you to send them a 4-digit code via your phone to allow access to any new unrecognized devices.

Agreed. Or a notification when a new device logs into your account, like Facebook does.