Posting this as a partial because I don't have time to devote half enough time to the wonderful array of clues provided, but I think the secret is
Take for example:
EDGBASTON: Comes up to a place near the M5, south of Eastington. If you actually want Edgbaston, keyword STODGY will get you there, specifically to the golf course.
keyword STODGY ...
To continue on from @Phylyp's work - they were first to realise the encoding mechanism for the message:
Using a very manual approach to the decoding, assisted by some Excel formulae which allowed me to keep tabs on the current possibilities for each letter, I have now fully decoded the initial message (punctuation mine):
What next? Note ...