as others have said, use testdisk directly from your phone. there's already a maemo port for it
but I doubt you can recover your contacts/conversation db though. as you've said, it's possible to recover data from formatted disk on PC. but problem is, you're not only formatting. you're copying new data to the same disk with flashing, so chances are those disk sector where your files were located has been overwritten by other files, and it's impossible to recover using software only
but it's not hurt to at least try though