I had the same problem. It occured, when a user downloaded a Office-Document in Record-State, changed it and uploaded it again.
I guess the reason is that, because some of the metadata fields are stored in the properties of the office document itself, while properties are not. And if the document is uploaded again, the metadatafields are imported again, but the properties set are missing. And the "Records"-function relies on a summary of metadatafields and properties. So Sharepoint believes the document is a record (because of the metada-fields), but cannot unlock it because of the missing properties.
I made some code, which was able to correct this
//necessary, because obviously the replacement file has been downloaded from sharepoint in Record-State
var siteId = currentItem.Web.Site.ID;
var webId = currentItem.Web.ID;
var url = currentItem.File.ServerRelativeUrl;
using (var site = new SPSite(siteId))
using (var web = site.OpenWeb(webId))
var elevatedItem = web.GetListItem(url);
Records.BypassLocks(elevatedItem, delegate(SPListItem item)
item[Microsoft.SharePoint.Publishing.FieldId.DeclaredRecord] = null;
item[Microsoft.SharePoint.Publishing.FieldId.HoldRecordStatus] = null;
item[Microsoft.SharePoint.Publishing.FieldId.IsLocked] = null;
item.Properties["ecm_ItemLockHolders"] = null;
item[Microsoft.SharePoint.Publishing.FieldId.IconOverlay] = null;
currentItem = currentItem.Web.GetListItem(currentItem.File.ServerRelativeUrl);
In my case that code is executed when a new document is uploaed. It checks if it is in Record-State, (which can´t really be for new Document). You could modify it to your needs.
In Fact the code bypasses the lock (because unlock does not work) and cleans the necessary metadafields by itself (in fact removing a lock manually).