High fantasy would be tricky. I was planning a game based roughly on a combination of Gaiman's 1602 and In Nomine at one point, which I thought would be amusing. The core idea of the setting was that due to (something - an imbalance in the world, the onset of Armageddon, a demonic plot, something), all the angels and devils that were on Earth were forced out of their bodies, but couldn't return to the celestial realms. Instead, they had to occupy living creatures whose souls were still in the process of forming - in other words, children who were still in the womb. As these children grew up, it was clear that something extremely unusual was going on, as they had all these freaky powers, but nobody knew where they came from. The spirits were without will, and didn't really have any coherent memory - they were mostly just raw power, creating children that were essentially mutants, a la X-Men.
Magic would exist, but would have been fairly low-key before all this happened. As time progressed, though, things started to break down without the maintenance that the celestials did. Magic started getting easier, and the laws of reality started to get less solid.
Over the course of the years after these freak children start getting born, the world starts to go to Hell. People start thinking the End Times are upon them, and a good chunk of the world breaks out into war. Mutants and mages are hated and feared wherever they go, as it's believed that they're responsible for the state of the world. PCs wouldn't know what caused the appearance of the mutants, or the source of their power. I probably would have had that as the major campaign plot, the discovery of the causes behind all of this.
Could have been a fun game. However, I ended up doing a Rokugan 1000 Years of Darkness game instead, which I'm really enjoying.
