If you are using your YubiKey with a service and/or application, the policy for lost or stolen YubiKeys depends on how the service/application deals with the situation.
The simplest is if the site supports alternative authentication mechanisms, so that you can regain access to the account and can de-associate the lost YubiKey from your account, and associate your new YubiKey to the account.
For example, the LastPass Premium subscription allows users to configure up to 5 YubiKeys with a LastPass account, so they can continue to log in using other keys if one is lost. Read more about it here.
If you cannot regain access, typical sites have an authentication credential recovery mechanism. You would use that to regain access to your account, and to dissociate the YubiKey and then re-associate it again.
Applications/services may also provide other mechanisms for users/administrators to assign a new YubiKey in the case the user lost his/her original key. Please inquire directly to applications or services supporting the YubiKey on their policies.
Please see also our blog post on this topic.
Posted in: 7. Security