You configured postfix to connect to remote destinations to ask them about recipients - as a requisite before you accept anything into your local queue.
smtpd_recipient_restrictions = reject_unverified_recipient
On a general purpose mail server, this is inappropriate for anything but domains under your control or with whose operators you have an agreement.
Asking remote servers for whether they have certain users without delivering mails will make quite a number of servers stop wanting to interact with you. Before knowing what you will send, they cannot easily tell whether you are a spammer trying to wash a list of his next victims or someone intending to deliver mail.
The simplest change to address that concern and solve your original problem:
smtpd_recipient_restrictions = permit_sasl_authenticated,reject_unauth_destination, reject_unverified_recipient
Because the restrictions are processed in the order specified, This exempts your authenticated users, and unrelated relay requests (rejected anyway). This way you can still enforce reject_unverified_recipient on incoming messages (where dovecot will presumably confirm addresses without delay). But without nagging remote servers about recipients that at a time you do not have mail for yet. You have to get more complex than this, though, if you want the feature also enabled for your users writing messages to each other. The ADDRESS_VERIFICATION_README file in your postfix documentation is.. a but old, but should still give you a general overview.
I generally recommend using the master.cf (which comes with suitable templates, at least in more recent times) to setup partially separated smtpd instances, one on port 25 for general internet use, one of port 465 for mandatory-authenticated user submissions. That way you can in a reasonably maintainable fashion enforce different rules on a per-service basis, further easing the task of treating relay traffic different from incoming traffic.
