It's always possible to completely clear the map, and in fact, there's quite a lot of leeway here - it's possible to have cleared every square apart from the dragon, and still have a healing scroll, plus up to about 10 spare gold.
It's almost always possible to get 303, but very occassionally, you will clear the map and still only get 302, which I believe is due to a glitch in the level generation system.
If you run out of moves late in the game, it's because you played "inefficiently" earlier on. Using a healing scroll while you still have hearts remaining, is the most obvious source of inefficiency, but not the only one.
As you have already realized, the higher your level, the more hearts you gain from using a healing scroll, so using hearts while you're still at a low level is inefficient. In general, you will spend 1 heart to gain 1 gold, but there are ways to improve on that ratio, or even gain free gold:
1.) Walls - there are seven walls, and the ratio of gold received : hearts used to destroy, varies as follows: 1:1, 1:2, 1:3, 3:4, 3:1, 3:2, 3:3 (so the average is actually very slightly worse than the 1:1 ratio of normal monsters). Ideally, you would destroy the two walls with a ratio better than 1:1 as early as possible, and leave the others until later.
2.) Chests - two of the chests contain 5 gold each, and they don't cost health to open, so the sooner you find them, the better.
3.) Mines - there are 9 mines, worth 2 gold each, and they don't cost hearts to destroy, so the sooner you destroy and reveal them, the better. Make sure you already know where the you-know-what is, by the time you have enough hearts to kill them.
4.) Gnome - gives you 10 gold, but only after all empty spaces have been revealed, so ideally you would mark as many spaces containing monsters as possible, without killing the monsters until after you've caught the gnome (also don't destroy walls until after you've caught the gnome).
In general, the main key to winning is to expand the revealed area as quickly as possible, as cheaply as possible - it's usually better to kill low-level monsters than high-level monsters (cheap), and better to reveal a space you know contains a low-level monster (even if you're not sure exactly what it is) rather than killing a low-level monster that was already revealed (quick).