Apple has device enrollment so you can get this with a brand new - out of the box Mac or iPhone or iPad. It could be a simple mistake where the person selling a Mac accidentally listed your serial number instead of the correct one. Or, or they pulled the wrong mac from stock for you. It could also be deliberate bait and switch or worse.
Actual mistakes where Apple or their agents mess up serials and DEP is super rare, and most of the time, this indicates a company purchased this through educational / enterprise / business team and your seller is the one that messed up intentionally or unintentionally.
I would get them to retrieve the original purchase and contact Apple to validate the serial number and double check they didn’t accidentally register your new Mac to the wrong account.
Since this is third party - have them release the DEP lock in less than a week or return it. You can’t escape this and without the original invoice - not your third party invoice, Apple will decline to unlock that Mac and release it in my experience. You might also consult a local lawyer to learn what your obligations are with respect to suspected stolen goods, you may have purchased an experience here and not a product you can use.