I've been doing some tests recently and have come to two conclusions regarding recovering lost data from the SxS Pro cards to which the Arri Alexa records:
1) PhotoRec is an amazing piece of freeware. In the course of my tests I tried DiskDrill, DiskWarrior, FileSalvage, as well as TestDisk(also made by the creator of PhotoRec, both available for download here). Not only was PhotoRec the only program that yielded any retrieved video files, it retrieved whole cards worth and then some. Not bad for a free download.
2) There is no way you're getting back data from an SxS card recorded to by the Alexa if you erase the card using the "Erase SxS" option. The results I got using PhotoRec were possible only because the cards were formatted using the other formatting option on the camera, "Quick Format". If you choose Erase SxS, the camera writes a null data(read a bunch of zeroes) over the card and blanks the card for good. At that point, your only option is to send the offending cards into Arri.
Further confirmation of these findings can be found here, where Michael Borenstein, Digital Service Manager at Arri Inc., restates the above in a thread in the arridigital.com forums.