While working on implementing the mechanics of the game I'm working on - a multiplayer RPG - I've also been brainstorming on the actual setting and wrote down a few lines.
I know it's not an actual story, but if any of you have some input it would be greatly appreciated :)

The setting so far:

Medieval-ish, high magic.
Current leading power is "The Kingdom" and its associated church, "The Light"
Several "dark lords", especially 1 greater dark lord "the king-pin" seems troublesome.

"The Kingdom" is actually established by an old dark lord who won (A former "king-pin").
Historical sources of how "The Kingdom" came to be have mostly vanished (destroyed or kept in a secret library).
Some sources still exist out there - and some people and things still remember. The player will discover that along the way.

Brutal and corrupt rule, hand in hand with an extremist church
The rising dark lord is a handy scapegoat - think Emmanuel Goldstein / Osama Bin Laden etc.

As a player you will be an outcast, part of "The refuse"
"The refuse" consists of outlaws, living in "The Kingdom" and surrounding areas. Mostly in secluded areas
- inspiration is drawn somewhat from Robin Hood's "Merry men" but their morality is way more gray-scale.
http://tvtropes.org/pmwiki/pmwiki.php/Main/BlackAndGrayMorality
No actual group - several clans. Some are allied, other enemies of each other.
Player-run clans are part of this "network".

Character class brainstorm - don't want too many similarities to Robin Hood, but here goes:

Cleric - Friar Tuck. Or perhaps more heretic-like. Worships "the light" but considers the official church corrupt.
Druid - worships nature and the old gods.
Fighter - Little John
Ranger - Robin Hood
Magic user ... Merlin-ish? (6-700 years earlier than Robin Hood - doesn't matter though)

It is a rather classic setting, nothing really new there. A dark lord and an evil Empire/Kingdom, corrupted church, player is a rebel.

It is not a bad thing, especially if the rest of the game is well built, but I personaly like it when the world in which I'm playing has something different from all the other medieval-themed game.

How is used the magic for example? What is the network of "refuse" you are talking about?

Thanks.
I've had some more thoughts about how to reveal "the secret" to the player - the fact that "the kingdom" is just a reign of a former dark lord.

I don't know if "the king" is still alive - perhaps he's the very same dark lord of ancient times that founded "the kingdom", perhaps an heir, or perhaps a puppet for the ancient dark lord who is now a lich or a vampire or something.

The player could start out as a normal citizen of the kingdom - certain actions would increase his notoriety and make it harder to get past cityguards without paying bribes. Some of these actions would be required to acquire power - it might be the case that a certain spell is only obtainable by killing some scumbag witchfinder general and rescuing a witch.

This way a higher level player would find that life becomes increasingly harder - no more easy trips to the big city, but perhaps with the option of visiting smaller outposts where guards are easily overpowered - or he/she could trade with the settlements of "the refuse".

"The refuse" is the kingdom's term for whoever it considers criminals. Some of them are indeed only that - while others also have more idealistic motives.

It is not a coherent group, but rather a patchwork of independent clans.

I'm actually not quite sure how magic is used, or how common it is. But I know it's illegal, except for official use by "the kingdom" and clerical use by the church.

Perhaps remnants of wizardry survives from the old times, guarded by age old wizards - or the advanced magic user could find forbidden spellbooks hidden away in unknown ruins.

I know there will be fireballs though:)

Druids of the refuse are keeping their old tradition alive - I don't have any immediate plans for implementing this class though.

Thanks - I have no plans of creating playable fantasy races. There will probably be fairies, giants, trolls etc in the appropriate places - mostly according to northern/western european tradition.