The prophecy must be cryptic, and illegible by everyone around the hero or heroes (save possibly the "Useless Guide").
The Villians stronghold is always dark and foreboding, eternally surrounded by dark clouds and storms. More often than not it is located on some pinnacle or at least set in the mountains where a single dusty, rock and skull strewn road leads upto a large black gate.
Of course he would not be the "hero" any more, but that would also be the end of the book . Just once...No work of high fantasy would be complete without the seductress. Sexier than "the girl" but with the loose morals and diva-like behavior that lowers her CHA, she is the biggest challenge to the hero. She thinks she's helping the villain, but is merely being used by him to distract or kill the hero. Expect her to die in the end either a) by the villain's hands when he's through with her, or b) in an act of self-sacrifice when she realizes she really loves the hero but he really loves the girl and she doesn't deserve him anyway.