Time Machine Full, But Only One Backup (or, what are .RecoverySets and why do they take up so much space?)

Okay, so I can't fully answer this issue but I'll share what I've found out:

1. Yes. Unfortunately Time Machine has deleted these, so anything unique that was in the past backups is gone for good.
2. The contents of .RecoverySets are copies of your Recovery HD. Ordinarily Time Machine shouldn't have more than one of these but, like you, I found the folder contained nearly a thousand identical sets. My best guess is that there is something wrong with my recovery partition that is causing Time Machine to think it has been changed, but that doesn't explain why Time Machine is creating so many copies without discarding any. I've filed a bug report with Apple, and I suggest anyone who encounters the same error does the same.
3. You can workaround this issue with a bit of light Terminal work:
   • First type cd /Volumes/{Time Machine Backup}/Backups.backupdb, replacing the part in brackets with the name of your backup volume before hitting return.
   • Next type sudo rm -fr .RecoverySets and hit return, you'll be asked for your password so that the command can delete your existing recovery sets.
   • Now run a Time Machine backup as normal using the menubar menu or by entering tmutil startbackup in Terminal and hitting return again. Wait till the backup is finished, as this will recreate your .RecoverySets folder.
   • Now type sudo chflags simmutable .RecoverySets and hit return, entering your password again if prompted. This will lock the folder (though it may not show this in the Finder), preventing Time Machine from creating any duplicate recovery sets in future.

The above workaround has a few caveats; firstly you won't gain any new recovery sets, but that's unlikely to be an issue, but if you're worried your set may be outdated you can unlock the folder using sudo chflags nosimmutable .RecoverySets (after cd'ing to your backup volume), delete your recovery sets, run a Time Machine backup, then re-lock it again. You may also notice errors in your console to the effect of "Could not backup OS X Recovery to…", but that's to be expected as you locked the target folder, it just means this workaround is doing the trick, so you can safely ignore these.

One further note; after deleting your .RecoverySets folder, you may not immediately see any extra free space in the Finder. The easiest way to do so is to open /Applications/Utilities/Disk Utility.app, unmount your backup volume and then mount it again, and you should see the correct free-space value, or you can just ignore it, as the free space should be there. In my case I freed up a massive 750gb by deleting my recovery sets folder, as I had over a thousand completely identical copies of my recovery partition in there (no wonder I only had 483kb of free space left!).

You may also want to investigate methods of repairing your recovery partition, but I'm not certain of the best way to do this; it couldn't hurt to at least try Disk Utility's first aid repair command.