Even if this is a client side problem in most cases, this doesn't imply we should not try to fix it nevertheless.

How about putting up a note like "in the case you don't receive a verification request via email, please confirm it's not in your spam folder and contact xxx [or: fill out a special form] for manual verification" or something like this?

This also allows to evaluate, if those incidents are really rare cases or part of "some of the major email provider consider our mails as spam in some cases" problem which would require to initiate additional action.