To my mind fantasy should be about fantasy: you fantasise. A fantasy writer should be free to allow anything into his or her novel from his or her mind. While a certain amount of internal consistency might still be helpful, it's not about keeping things plausible or nearly plausible, or sticking to the rules (like, say, hard sci-fi).
This is why I'm bringing up Perdido Street Station - it's brimful of highly original beings and events. The setting combines magic and steampunk; the world includes all manner of creatures and hybrids - to give you some flavour, the heroes, a journalist (with a beetle instead of a head), a freelance scientist and a criminal fixer are trying to defeat a giant dream-stealing moth, that should give you a start. The setting - the city of New Crobuzon - combines the absolute worst excesses of every major city on Earth. Mieville has a wonderful prose style that describes settings in three-dimensional, 32-bit colour and HD resolution; and he's never happier than when finding new and fresh ways to describe just how mucky the current setting is. And there's not an orc to be seen anywhere.