To me, having to tag that eaten deer would be like having to stop hunting because you wounded a deer and couldn't find it. How many hundreds (nay, thousands?) of deer get winged every year during the hunting season, and because of poor tracking conditions or whatnot, are never recovered?
I guess you could play the honor system and hang up your bow or gun, but I'd wager a pretty large sum the majority of folks in that situation just keep right on hunting until they actually put their hands on a deer.
And if you're in the minority who are that honest, you're probably also honest enough to call the G&F to tell them you found your coyote-eaten deer, and they'd say "unfortunately, sir, you do need to tag that deer because your license does not guarantee the condition for which the deer you shoot will be in once you find it."
This is straight from the G&F website:
https://gf.nd.gov/news/3408
I shot a deer, but it is rotten. What can I do?
You must take possession of the animal by tagging it. A license only allows you the opportunity to hunt. It is not a guarantee to harvest a deer, or to the quality of the animal.