There seems to be a lot of confusion regarding what verification is all about. I'm going to list out what it means, based on my reading of their documentation[1] and on what worked for me. It includes some essential preparations that you
MUST TAKE if you have access to your account. This is to ensure that all your devices are verified, that they all have access to all encrypted messages and that you don't ever get fully locked out.
DISCLAIMER: I have no direct experience with Matrix or Element code base. I have no affiliation with them either. So this isn't official and a few errors can be expected. Please let me know if you notice any. I will keep this corrected for as long as I can. Otherwise I'll add the errata as child comments.
1. Matrix has TWO levels of authorized access.
2. The first level is where you enter your regular username and password, that's unique to your homeserver (like matrix.org). It looks like OIDC/OAuth2 to me. On being authenticated at this level, your client (Element, Fluffy, Cinny, etc) is able to access the messages meant for you. At this stage, you're able to read any unencrypted messages. Most community chatrooms are unencrypted by choice.
3. The encryption used for your encrypted messages is end-to-end. Their encryption keys are named 'room keys' in Element (there are several of them). They are not directly available to your homeserver (otherwise, it wouldn't be end-to-end). Similarly, there seems to be an 'Identity key' (presumably a cryptographic private key that makes you the owner of the account and is needed for some account operations). This key is also not directly available to the homeserver.
4. The client app just logged in and the server doesn't know your room keys or ID keys. They're known only to your other clients. So now you need to transfer them from those clients to the new client without divulging them to any servers in between. Once that's done, your new client will be able to decrypt all your encrypted messages and join those discussions.
This process of transferring your room keys and the ID key to your new client is the second authorization step known as 'Verification'. (I presume it's called verification because your new client can now prove its authenticity using your ID key.)
5. Verification can be done in three different ways. The first two are manual methods and are rarely used. We will discuss these two later. The other is using a 'verification request'. This is straightforward. Your new client requests the already verified clients attached to your account for your room and ID keys. Any verified client can respond. However, it needs to first verify that your new client is really yours, and not someone who used your leaked password or hacked your account. To do this, the clients currently offer you two methods - one using a QR code and the other using a sequence of icons.
If you select QR code, your verified client will show you a QR code that you need to scan with your new unverified client. Since it proves that both clients are in the possession of the same person, the verified client then proceeds to transfer the keys to the new client, finishing the verification. Now if you chose the Icon sequence instead, then the verified client creates a random sequence of icons that it sends to the new clients. Then both the clients display it to the user. If the user accepts on both device that the icon sequences are identical, it's the required proof that both clients are with same person. The rest of it is the same as before.
6. So far, so good. If you were able to complete till step 5, the new client is verified and now you can carry on with your business. Now we address the situation of what happens if you are not able to do any of these. Just assume that all your clients got logged out together for some reason (yes, it has happened before). Now none of your clients or the server has any of the room keys and the ID key needed to prove your ownership (crypto authn) or access your encrypted messages, even after you log back in. The only solution is to load the room keys and ID key from a backup. This is why it is IMPORTANT TO BACKUP your room and ID keys.
7. There are two ways to backup the room keys and the ID key. These two methods are also the two manual methods of verification that I mentioned above. The first method is to back up the keys on the homeserver itself. It's convenient because all your clients can access them at any time and keep the room keys updated as they change or new ones are added. This feature is called 'Key Storage' in Settings/Encryption tab of Element. It's enabled by default. ALWAYS keep it enabled.
You may be wondering how it can be end-to-end encryption if the private keys are stored on the homeserver itself. If you're, then you're correct. They are stored in encrypted form on the server key storage. The decryption keys for that is available only to the clients. So while the server holds the keys, it cannot access any of them.
8. Here is your first opportunity to do something about accidental losses. The decryption key for the key storage can be downloaded and preserved in a secure manner. Perhaps write it down on a paper or put it in the password manager. This key is called the 'Recovery key'. You can download or change it from Element's Settings/Encryption tab. ALWAYS BACKUP YOUR RECOVERY KEY.
You can use the recovery key instead of the QR code or the icon sequence to verify your new clients. There are two differences from the previous method. The first is that you can enter the recovery key directly into the new unverified client. The verified clients are not needed here. The second is that this is possible even if all your clients gets logged out. Again, this is why it's very important to BACKUP YOUR RECOVERY KEY!!
9. Besides setting up server key storage, you can take one additional step. This is the second manual method of verification. You can download and backup all the room keys and your ID key on your local system. This option is available as the 'Export keys' button on the Settings/Encryption tab. When you do so, you'll be asked for a password. This password is used to encrypt the file with all those keys, so that they don't sit unencrypted on your disk. This file can be backed up as such, but you can encrypt it again if you prefer.
You can use these keys also to verify your account. You'll need the above password to decrypt the keys file. However, this method still has one big CAVEAT. I suspect that the keys file need to be updated regularly, since there will be new keys when you join rooms. So if you use this method to validate, it's likely that your client won't be able to decrypt the rooms/messages for which it doesn't have the copy of their key. But this is still worth doing, because it contains your ID key which can be used to verify all your devices again as a last ditch measure (if your homeserver happens to quit or something).
10. Now let's just say that you're a careless ### who didn't do any of the above. You still have the option to nuke it! That is to Reset your cryptographic identity from Settings/Encryption. I presume that this just discards all your previous keys and creates a new private ID key. Since all the clients can now access this key, your account is verified again. But you will not be able to access any of your previous encrypted conversations. And the homeserver helps you along by discarding all your previous conversations, room subscriptions and settings. So now you're left with a cleanly empty account. But hey! You have your verified account back!
So, in summary:
1. Always verify all your clients
2. Setup server key storage (it is enabled by default, don't disable it) and backup the recovery key
3. Backup the room keys and ID keys on your local system. Use it for recovery/verification only in the worst case
4. Don't forget the password you used to encrypt the above file (just sayin)
NOTE: I intentionally left out some crypto details from the above (like session keys) to avoid making it any more complex. If you're unhappy with those omissions, please just leave a comment.
[1] https://element.io/en/help#encryption