One idea here is mystery. Your brain is built to want answers and completion. So if your game is just a series of Tetris levels, well, the only reason to pay for it is if you think you can't find more free tetris levels (specifically point being: doesn't matter if they like your game! Even if they do, they don't need to buy it). But if your game has a storyline and leaves the demo with "Trapped in chains, with Dr. Reducto closing in, our heroes see no way out...", then (if they enjoy it) they almost have to buy it. They need to know!

That works with story, but there's also gameplay surprises. Perhaps show a gigantic scary boss in shadow. Something to show them that, if they buy, they'll get to do something no other game gives them (yeah, lots of games have big bosses, but none of them have that boss! Which we hope is a unique and interesting one).

I think what it boils down to is: don't make a match-3.
 

I remember wanting to improve my game of Pac-Man just to see the little cut-scenes (back when cut-scenes were A New Idea). Then I watched someone else play through it to levels I couldn't hope to reach, watched all the little intermissions, and suddenly my motivation went down a little bit.

I don't think I ever got past the second intermission.

I guess the trick is to create something COMPELLING - and leave them wanting at the end of the demo. Compelling isn't easy. I have played Planetary Defense. It was cool and fun. And it was kind of unique, too - missile command around an entire planet. But it's one of those games that I never used up the time on the demo. There wasn't anything particularly compelling about it. It looked like it was going to be more of the same. Compelling to me means always wondering what comes next. Like you said - storyline-based or regular visual / gameplay rewards.

But those match-3 games keep selling. My wife keeps playing Pretty Good Solitaire - often the same games - just 'cuz. So I don't know if everyone feels that way. Again, it might be a male / female thing.