In a normal scan Recuva looks sequentially through the MFT for records that are flagged as deleted. If Windows is allocating new files for either user or system purposes then it will also look sequentially through the MFT to find the first available record to use. If it uses the record that was holding the info about your deleted file, then that info is overwritten and Recuva won't find it.
You may be able to find the file with a deep scan, it will have its extension even if the file name is lost. However if the file was fragmented then it is unlikely that any more than the first fragment will be found.
If the file was larger than 4gb (avhd files seem to be large) then a Recuva normal scan might find the file name, but all the addresses of the file data will be lost, as NTFS overwrites them. Then you're back to the deep scan.
I think you are, as you elegantly put it, boned. A avhd file is possibly over 4gb so the normal scan wont find any data, and its also likely to be fragmented (as its a large file) so a deep scan won't help.