We provided proof of address, some in Joint names some in Mizel's maiden name and some in my name and a short cover note explaining that was all the proof we had at the time. Extra evidence certainly doesn't hurt.
As expensive as it was, I'm so glad we went up and got our answer straightaway. Months of not knowing would be too much to bear.