Lots of suggestions here I haven't heard of before, thanks everyone. More welcome. I am not a platforming god, so I'll probably stay away from the ultra-brutal ones.

What specifically bothered you about the save mechanics?

I'm not sure how the game is separated, like maps or levels but I played a few minutes then I died and I had to start from the beginning. I guess I didn't even reach a save. How does it work?

I second Super Meat Boy, quite hellish of a platformer.

Cave Story + ?

Project Black Sun and Cave Story+ take the icing in my opinion, along with Braid.

And then there is this: http://deepaksave.us/play
It is free and found it on RPS

As far as I know you have to beat a few screens without dying until you reach the next savepoint. The first might be 3-5 screens away, I don't remember exactly. Any upgrades you find are saved even if you die, you don't have to get them again.

Thanks guys, I'll definitely reinstall it when I've time.

Another vote for VVVVVV, although there is no combat involved. It's challenging for sure, but not in a dicky kind of way. "Tough but not unfair" probably describes it well enough.

It's also got a kickass soundtrack.

dark void zero, this game is good but damn it kicks ass at difficulty

http://store.steampowered.com/app/45730/?snr=1_7_suggest__13

Eversion. There is a Steam release too with better graphics.

Definitely Mutant Mudds

I'd add my recommendations to Super Meat Boy and VVVVVV, but you said you weren't interested in 100% pure platformers without combat for whatever reason, so I won't :)

Bunny Must Die is a very good Metroidvania, though the jumping mechanics take some time to get used to.

Taijou has a free beta you should definitely look into - a platformer / bullet hell hybrid sounds right up your alley :). There was a beta available but I can't seem to find it anymore. http://steamcommunity.com/sharedfiles/filedetails/?id=93162400

In a certain regard, maybe Fortune Summoners: Secret of the Elemental Stone might qualify, too? It's a JRPG hybrid with leveling up, minor item management, dialogues and the occasional simple puzzle, so it's probably not quite what you're looking for, but the underlying gameplay mechanics of the game are side-scrolling 2D platformer + action combat, including bossfights. Then again, most people who describe it as hard are actually ranting about the controls (I've found it rather easy once I got used to them and I'm by no means a hardcore gamer). Anyway, the Carpe Fulgur website I linked to also has a free demo.

No special reason, since pure platformers and puzzle platformers are awesome too. Combat platformers just happen to have my attention right now. I'm craving bad guys and boss fights as well as spike traps and fire pits.

I still welcome the recommendations from other subgenres, though. Finding new games is a great thing.

It's too bad they never released Outland for PC. You'd probably like that one...