Around here Holly self-seeds under Cedar and Douglas Firs rampantly. They seem to tolerate quite a bit of shade in those situations but are more open growing. If you are wanting a tall privacy, why not Thuja 'Green Giant' http://davesgarden.com/guides/pf/go/80097/ which grows fast, can tolerate some shade and is evergreen.
That looks a lot more like a rub than a meal - and was that T. occidentalis or T. plicata? I have many T. plicata (including several aptly named 'Deer Proof') that have never had a smidgen of nibblin'.
Can you give an approximation to "tall privacy"? Short people want to know...
Also - how much horizontal space is available? There are a number of evergreen Viburnum selections that make great screens, including V. x rhytidophylloides 'Alleghany' and V. x pragense. Both are relatively rapid growers.
Resin, you're right - definitely antler abuse. VV, it's thuja occ Degroot's Spire.
I have several (I was trying to create some hedging) and all are ravaged by antler rubbing.
I have to protect my saplings with trunk protectors, but it's hard to do with a densely foliaged evergreen!
They particularly seem to like thuja's for antler polishing.
I have had the same experience in multiple locations in my yard.
Here's another set of thuja's with the lovely foliage pruning pattern courtesy of the deer.
Most of those fine viburnums listed are really good ones for relatively benign climates like Vancouver, BC or Seattle/Oregon Pacific northwest areas. You'll find some of them further south in the eastern US, but not terribly often. The colder winters and hotter summers are not very friendly to these plants.
All that said: I would still encourage you to try every evergreen viburnum you can lay your hands on, and learn what works for you. The choices I listed should be solid backbone plants, around which you may wish to try the more tender ones from the article posted.
Depending on how big a plant you want to start with, you could do worse than have a conversation with the fine folks at Classic Viburnums (in Nebraska).