What do we do when someone sends a card listed as Near Mint, but it's Played at best?
What options do I have?

First, bring it up with your trade partner. If they won't work something out with you, open a BTR.