I've seen so many people moan about the lack of restart and eventually it transpires that they've only either read reviews or played the demo. It really isn't an issue in the full game at all.
Burnout Paradise is definitely up amongst my favourite games of recent and what's even better is that the devs seem devoted to supporting it for a decent amount of time adding worthwhile content. Admittedly I haven't played it for a while (so many games, so little time), but I'll certainly be returning for the new content patches.