In all honesty, I think Jo has said the main feature of a roguelike in the past. Permadeath isn't important, it's the fact that you have to learn from your mistakes, and that the player them self must learn new skills to beat the game. If you can beat the game first try, it isn't a very good roguelike. If it takes them a couple dozen tries, and the game has the content to make it continue being fun, that would be a good roguelike.
I'd say a good example would be a roguelike with multiple dungeons. If you die, you are sent back to town and have to restart the dungeon, and hopefully you've learned what caused you to die the first time down so you can avoid it the next time.
Also, I still laugh whenever people say Rogue isn't roguelike... That's like saying Diablo isn't diablolike, or Linux isn't *nix.