DEP Enrolled Mac + New Logic Board = non-DEP Mac (right?)

Not if they correctly re-serialize the board. Then it should re-DEP as normal.

Same way you can spoof a serial in a VM to get it to DEP for testing purposes.

Sounds like they should have added the original serial to the board upon repair? Some google checking seems to indicate that is possible, but not always done. In this case it looks like it may not have been done.

Yes they should have, they have a board re-serializer. I would absolutely complain that they did not apply it because this does knock the machine out of your DEP list without the right serial.

They should be able to reserialize it for you after the fact or there should be some other way for them to rectify this (add the new serial to your DEP list for example).

@DougE Yes, as @hkabik affirms, when you replace the main logic board in a Mac device it prompts you to re-serialize the hardware... However, in my first-hand experience I've seen peer technicians skip this part or enter fake data like "newserialnumber" out of convenience (or n00bness or laziness, whichever). The iOS application MobileGenius the Apple technicians use allows you to scan in serial numbers, a lot of times people scan in the wrong number or whatever SKU they see not taking into consideration the aftermath.

Having worked at apple, it should have been re-serialized. if you go to about this mac, and see no serial number, they missed a step. Take it back and have them serialize it. If they did not put the correct serial in, it needs another mlb replacement.

If you don't have them re-serialize the board you will run into other strange issues as well. I remember a lot of techs when I worked at apple would forget and customers would comeback and time machine back would fail.