Is this possible, and how hard would it be?

[llamabeast]

You can make special magic sites and hide them on a map, but you can only do things that sites currently do. So perhaps rather than giving you an item (no sites do that), the fire site would allow you to recruit an awesome fire monster or fire mage. As for the messages part, you'd just agree with all the players beforehand that they had to announce when they found one of the powerful sites.

Edit: Also, I meant to say: sounds very fun!