But it also asks for recovery key and complains about it being out of sync until entered even if you do the verification step! Entirely possible to only get a partial recovery of messages until this is entered.

That's not normal. It doesn't happen on any of my accounts or clients. Verification takes a moment if you're in a lot of rooms, but it exchanges all keys.