whenever the player gets hit, the game becomes a little bit easier, whenever he defeats an enemy, it becomes harder.

Games with dynamic difficulty are often vulnerable to playing bad on purpose. Be careful of that.

Do you have any ideas?

You could do like System/Bioshock and have the player regenerate from a save station without reseting anything in the level. Or Descent where they also drop all their upgrades where they died. Or like Chip's Challenge and offer to let the player skip the level if they fail too much. Or like Kirby's Epic Yarn and have the player losing beads/points/something other than lives.

I understand your concern of sending the player back to the beginning of the level or having him go through a "You lost all of your lives, Game Over" screen.
He will still try to play through the same level anyway, so it is a waste of time. Instead of having all the ceremony, just let him try again in the quickest way possible.

To answer your question, it seems that the most engaging way to have negativity in your game comes not through punishment, but through rewarding. That is, the negative force in the game comes from the player not getting the reward rather than being punished for failing.
Bill Roper, a game designer who worked on several Blizzard games, discusses this as the "Carrot vs. the Stick" principle.
In this horse racing metaphor, it is the difference between having some form of punishment that forces you forward (the "stick") and some form of reward that drives you forward (the "carrot").

[media]http:[/media]

It falls onto you the burden of adapting this to your game design.

EDIT: Another source for inspiration and theory is the free GDC content archive. I suggest you turn off all filters except "Design:"
http://www.gdcvault.com/free

You could do like System/Bioshock and have the player regenerate from a save station without reseting anything in the level. Or Descent where they also drop all their upgrades where they died. Or like Chip's Challenge and offer to let the player skip the level if they fail too much. Or like Kirby's Epic Yarn and have the player losing beads/points/something other than lives.

Or like the Crash Bandicoot games, where they gave you that extra protective mask when you died consecutive times. Or like the Heart of Darkness game, where they would reveal which special move was needed in a certain part after you had failed on it several times.

The game I'm currently creating is a platformer built around speedrunning. The primary goal is to beat a level as fast as possible. Because of this, I punish the player by slowing him down. If he gets hit by an enemy or obstacle, he stumbles and loses momentum. If he happens to fall in a bottomless pit or gets hit by a fatal attack, he will restart shortly before that particular obstacle almost immediately, but the timer won't reset.

I think you need to shift your focus a bit. The thing is - you don't want to go and "punish" the player for not being as good as he should. Instead, you should look at it from this prespective - you are giving the player a chance to reiterate what he failed at, so he can master the needed skills to go past that. This is what the entire situation with "sending you back" does - it reverts the player's progress to a point where he has to rethink and improve on skills in order to go further. To illustrate - the games, that actually really frustrate the player are those that throw you way back after you die or mess up the mission. It's frustrating because you have to repeat things that you already have gained the skills to do and you can't focus on the things you need to obtain ... so you fail again and again and ultimately - quit the game. The proper way to do this would be to split your level or mission/quest/task sequence in segments that help in building the player's learning curve. Once a segment is fully passed, the player should not have to play through it again if he messes up in the next segment. The segments should be fairly short, as having long segments often defeats the idea of having them in the first place.

Prince of persia did it nicely I think, where you could rewind time if you were about to fail, or had a companion that picked you up if you fell down.

The point of that game is to progress through the next part of the puzzle, and having the player not having to redo the same puzzles too much kept the flow up.

I guess that's just making sure the "save spots" are close enough.

A little bit of frustration is good though, it can trigger the player to enjoy it more when (s)he finally succeeds, but it is a fine balance...

to many players less than perfect is failure.

Oh, can I relate to that. In just about any game with quicksave, the every time I take a hit, reload. When I played SWAT4, I remember being glad the game put me back at the beginning of the level every time I lost, just because it kept me from doing this. Of course it was also insanely frustrating, and I gave up part way through the expansion.

The challenge is to find a way to get the player to accept a sub perfect or even a sub optimal playthrough.

This is an old game, but Wing Commander required the player to go on missions with various NPCs. If a NPC died, he or she was gone. I think missions also had varying levels of success. If you failed a mission, the story line would turn dark, and you would have to go on an alternate mission path to work your way back. I remember some of the missions being so challenging, that I would just sit back and say, "Whew, that's as good as I can do, let's see where I go from here."