As far as randomizing monsters I think it's not biggie if the same monsters have the same stats every time. This allows players to get better at your game, as they know what they are up against.
The variety and replayability comes from not knowing when or what monsters you'll be faced with. Also throwing in the odd 'out of depth' monster can be fun. Fate likes to throw in the odd 'elite' style monster that is like the normal version but tougher, or has a random ability or immunity.
So I guess I'm saying most games that do it really well are those that toss a curve ball once in a while.
Random Realms randomizes monster stats and names each game, and introduces a new monster each level. So level one will give you an 'A' to fight, level 2 a 'B' and so one. Between levels you get a heads up about the monster you'll fight next. I'm not sure if out of depth or elite special monsters are used in Random Realms, but it's the game I think of when guys want to talk about randomized enemy stats.
As far as randomizing item stats, that can be fun. Like giving each mundane item a chance to have an enchant and occasionally an 'artifact' will have several enchants. Random enchants each time. The issue here, obviously, is you might be randomly creating complete junk.
There was a 7DRL that did something along these lines this year. Well of Enchantments? I didn't play it, but each item (and creature?) was created from the same class. Maybe check it out. If you are pretty code savvy the source code would be neat to read. I'm not so code savvy, other people's code makes my eyes bleed. :-)
As for randomized quests, or even a randomized win condition, I point to the game Fate. You should really check out that game. The original game is best I'd say, you can find it cheap or even free somewhere. It's a single dungeon, single starting town, randomized item stats, randomized main boss enemy, randomized quests. No classes, you can gear up and stat up anyway you like. If you beat the game you can hand down an heirloom item to your next character, but you don't even need to quit when you beat the main boss. You can keep going, it'll keep making harder and harder monsters and what not. It's not a perfect game, but it has a lot of interesting qualities.
Randomized quests seem totally doable and interesting to me, it's just tough to make them interesting. Side quests are rarely interesting anyway, I find making the END GOAL of the game different each time to be very very interesting. Slay the Dragon this time, you need to load up on fire resistance. Slay Dracula next time, better find a lake of holy water to dump him in. The next time it's a Hydra, blunt weapons are good, but a scroll of multi-fireball is the real winner.