As part of Request's Test Payment feature (→ Test Payments Overview), Request checks your payment and verification history to a recipient's wallet address. The outcome of this check is displayed next to each wallet address.
"New Wallet" → You haven't (test-)paid this payment method before*
"Previously Paid" → You've paid to the payment method in the past as part of a regular payment (e.g. you paid this wallet when you paid a previous bill from the same vendor)
"Wallet Verification in Progress" → You've initiated a test payment, but the test is not yet complete (e.g. because the recipient didn't yet confirm that they've received the funds)
"Wallet Verified" → The recipient confirmed that they can access the funds sent as part of a test payment you made
*A payment method here is a unique combination of wallet address and network. If either of the two are changed, then the wallet will be recognized as a new wallet. This ensures that exchange addresses, which can differ per network even for EVM networks are marked as new.
Here's how the wallet's verification status looks on a bill:
