Wow, great ideas! I would like to add some challenges:
Easy:
Decoy: Every time you open a chest, fireworks explode 10 blocks above the place you are. (They deal no damage.)
25 experience and 50 points.
I see dead people: Every time when you kill someone, a skeleton spawns at the place where you killed them.
25 experience and 50 points.
Medium:
Afraid of running: You can't run.
75 exp, 100 points.
Everything I touch turns to... sand?
Every block you touch with your feet turns to sand. That means that you have to come up with new strategies to build to your enemies!
75 experience and 150 points.
It's alive! It's alive! When you open a chest, a baby zombie that rides a chicken will follow you.
50 experience and 75 points.
Lumberjack/Here's Johnny!: You can only deal damage to players using an axe.
100 exp and 100 points.
Hard:
Ouch, it hurts: Every time when you kill a player, your maximum hp will decrease. So when you spawn, your maximum hp is 10. (Unless you eat a golden apple)
If you kill someone, your maximum hp will be 9. When you kill another player, your maximum hp will be 8, etc.