Can't find Excel 2011 Auto-recovered spreadsheet
Finally we found the file in the folder:

/Users/username/Library/Application Support/Microsoft Office/Office 2011 AutoRecovery


As the /Users/username/Library folder is a hidden folder since OSX 10.7 and not by default searched by Spotlight it's incredibly stupid that this folder is auto-suggested when saving a recovered file.