Fast forward to last night. In browsing, I discovered that the resting place of several of the Yorks, including the one I sought, was in the church at Fotheringhay. A currently still active church. We'd driven by this church, and I even have a picture of the church from where the castle once stood. I was that close, and didn't know it.
Our friend M told me this morning that at the time we were there the church was under renovation and wasn't open for visitors, so I feel slightly less frustrated.
But next time we're in the UK, I want to go to Fotheringhay again. I also want to visit Middleham, but that's a story for another day.