Someone may have owned or used the computer before you, even if you bought it “new.” It might have been purchased and returned and resold as new without your knowledge, and not properly removed from a prior associated Apple ID, perhaps. It might have been purchased fraudulently by this hypothetical prior owner. Or your purchase may have been flagged as fraud post-sale by the vendor for unknown or no reason, and reported to Apple as stolen by said vendor.
Apple will be able to help you with any of these concerns, if you are the legitimate owner. I don’t mean to offend, or to imply or to suggest you are not. All Apple needs to prove ownership is a picture of your receipt or a screenshot of the invoice if purchased online, whether from Apple or a third party.
If that's true, couldn't someone just print out a fake invoice, with no way for them to verify it either way?
https://arstechnica.com/gadgets/2020/06/local-authorities-wi...
It's inconvenient, but life is inconvenient. Such is the way of the world.
While it's true that this sort of thing shouldn't happen, your comments here seem to indicate that your big blocking point is that you don't want to talk to a human being. You want 2FA or magic links or some tech-focused hands-off method of resolving your problem.
Real life isn't like that. Sometimes you actually HAVE to go down to the DMV, or the post office, or the county clerk, or the returns counter at the store. The world is not the ideal tech utopia that the SV bubble has sold us. It's still run by wetware. Sometimes you have to just go through the motions instead of having a hissy fit on social media.