When I got purged from my old GP's list years after my move to FH, I found myself in your predicament. I telephoned several places only to be told that they were full or I was outside their catchment area. When I telephoned the centre which was my first choice, I was told that I was out of the catchment area despite the fact that my lodger was a patient as was the neighbour across the street!
No-one would take me apart from an appalling practice, ironically, a stone's throw away from my old GP. After 6 months, I had enough and showed up at the first choice centre.... I made a polite enquiry about becoming a patient and I was registered on the spot and no hassle!
I think when people telephone about registering, they just get a brush off but it's harder to turn away people when they're on your doorstep.
Good luck.