It sounds like you had good luck with the software you tried, but I wanted to add that the one time I accidentally formatted a card like that, I had good luck with PhotoRec.
http://www.cgsecurity.org/wiki/PhotoRec
If I remember correctly, it even recovered some files several formats old (due to not having been overwritten in the mean time). Though I think there was a minor issue in that it identified my CR2 files as TIF's, so I had to rename them. That was a couple years ago, and it seems to get regular improvements, so maybe that's not an issue anymore.
--Greg