Make it secretnext. In the map, a secret exit could be marked as "new game+".
Heck, you could script it to increase the difficulty. We could have hidden difficulty settings that make monsters tougher and tougher. Maybe even some monsters filtered for very high values only.
I support this. Making monsters scale based on a difficulty modifier is something I've actually made previously. You would need to tweak the decorate a wee bit, but you could easily pull this off.
One of the other things I was thinking about for re-playability was to have perhaps a passive score system of some kind? It would be a simple kind of thing that would stick around for as long as the user is in a session.
Also, mixing spawns up is something that would be feasible, but would be a LOT of work. I wouldn't really suggest it unless you really wanted to do something crazy.