>>5 I don't consider it a true win until this has been accomplished anyway!
I don't know if it counts, but a restraint I place on myself usually is to never have a pokemon above the level of the gym leaders' or elite fours' pokemon. If one of them accidentally levels beyond it, I try to use one that I haven't yet. It forces me to use a more diverse and interchangeable party, and also makes a good excuse to go back a few zones to take care of unfinished business :u
I tend to break the rule for the elite four in the earlier games though, since rather than all of them being within a certain range, they scale up as you go on. I remember in Gen II, the levels would range from 50 to 65 or something, so taking it on with all level 49's would be ridiculous, especially at Lance.
In terms of challenges though, I haven't done it myself, but a common one is the Type challenge. It's what it sounds like - you can only use pokemon that have a certain type. Dual-types are fine, as long as one of the types is the chosen one.
An even more restricted one is the single pokemon challenge, where you can only use a team of one type of pokemon (and their evolutionary line). Kind of forces you to be creative about dealing with things, like using unusual movesets.