Hi,
if you really will have 500+ levels, then maybe you shoudl organize them by chapters at least, and then I would use a file per chapter hosting all levels data for that chapter.
we currently use xml in a game project done 100% in playmaker, and it works well, we define content at edit time, load and save data when th euser is playing. But in your case, easy save will do the job very well too. Xml requires some proper understanding of xpath and can be tricky if you don't have experience with xml to begin with. But the great advantage of xml is that it's plain english and so it's a lot simpler to debug, even on the device since it's a plain file that is readable.
Bye,
Jean