While everyone may share a wallet on an exchange, they still have their own separate addresses. Verifying an exchange address would be no different than verifying a personal hot wallet address. Ask the users who sent from exchange address to withdraw a very small amount from their exchange wallet to verify. After verification, send refund back to that address. Then the user receives their coins back on the exchange where they originally came from.
Not all exchanges do it this way. The address it "leaves" from is not the same unique address within the user's account.