I know what you mean, Sol, but like everything in RPG making, it's just a matter of work. Write, test, re-test, leave that section for a while, work on something else (the battle system or whatever)...come back after a little while and I bet you'll notice straight away the bits that stand out in your plot and dialogue as being unnatural\forced\corny\cliched\whatever.
No, it isn't just a matter of work. It's a matter of know-how.
If you don't know Ruby, you can't script, no matter how hard you work at it. Writing is the same way - I don't mean just knowing the words and basic rules of the language. Real writing has as many rules, guidelines, exceptions, and anything else you can think of as any other craft (a craft that has been developed over centuries, I might add).
For some reason, writing has fallen out of view as difficult, along with most other "liberal arts" majors in colleges, but in the real world, writing well is extremely important, yet few people seem to be able to do it well. If you work with software, you'll encounter it in the documentation of most "free" or even "open source" software - it sucks (Eric Raymond even wrote an essay on the topic, though he completely missed the cause). "Professional" software houses hire technical writers to produce their documentation for them, because they know it's value and importance.
Back on topic: Writing a story for a game is very similar to writing a short story (possibly a novella). You need plot, character development, dialog that makes sense and moves the plot forward, and to make it even harder, you have to give the player the illusion of choice and freedom as they read the story (even if it does has multiple endings, the player ultimately has to follow the rails you laid, or else never "finish" the game). And fiction writers are constantly learning: workshops, retreats, writing circles (even professional, published authors). Like any craft, you never truly master it - there is always something else to learn and room to grow.
If you still think cliche's are the problem, try this: Write a game without using "The Reluctant Hero", "Redemption", or "The Quest".
If you think "The Quest" isn't fair on that list, substitute "The Messiah".
Edit: Seriously, think of all the RPG's you've played. How many of them don't use one of the themes / plot elements I just named?
Moar Edit: My wife, whom I've enlisted to help with the writing and dialog just showed me the program she uses in her writing: Some commercial product, I forget the name. It keeps track of all the major characters, with room for everything about them and notes for plot, development, etc. A major plot timeline, which links to smaller plot elements so you can keep every dialog and scene separate for easy editing and changing. You can make mind maps to help see how everything ties together. A section for locations, the setting. Pretty much anything I could think of and then some.
The actual typing in the lines of dialog and narrative is probably the smallest and simplest part of the writing process.