Valkyrie profile covenant...

Read the stickied FAQ to find out how you can find out what the correct savetype for a game is and then set the game to run on that.
Some games load on the incorrect savetype, but then make unstable or unreliable saves as those you mention which the game sees fit to erase when loaded.
Alternatively you could be using the correct savetype for the game, but whenever you first load the game you start on an incorrect savetype and some games when accidentally loaded with an incorrect savetype automatically erase whatever save file there was for them.

what version of no$gba are you using? If it's the 2.6, you need to find the correct savetype on no$gba settings. If using 2.6a, then just set it to auto. Or are you using cheat codes? It can be a problem too, as using some cheat codes may corrupt your save files.

EDIT: Gah!! Schumi, You beat me by two minutes