There should be Trolls, Leshy, undead, poltergeists, random mystical/magical enemies you can encounter like the ones featured in The Witcher (slavic mythology ftw). You wouldn't meet these everywhere on the map, and finding one of them would be a long, hard task (a hunting party would either have to ask around in IRC or use some magic super-expensive collective numen spell or whatever). Killing such a creature would even be harder than finding it, probably impossible to solo.
A bit more "casual" would be the implementation of grizzly bears (black version of regular bears, hurr) with levels 11-30 or so. Maybe even crazy stuff like Dire Boars and Dread Wolves. Just take a look at how D&D solved the problem of wildlife getting too easy to slaughter at higher levels
