I've purchased them at Radio Shack before too. They are are a purlply-pink colour with green trim made by Tadiran. It should be easy to spot on the rack.
Not all the stores carry it but the larger ones usually do.
You could also try some of the Mac dealers in London like Mostly Mac or Mac Outpost. You'll be lucky to find anyone selling these for less than $18 to $25. If you want it cheap you will have to search the mail order route. That doesn't help when you're in a hurry.
Thanks to everyone who replied. After the notes that some had found the batteries at Radio Shack, I did some looking on the Radio Shack website.
Indeed - Radio Shack sells them for $16.99.
I used the website to lookup what London stores had the battery in stock. Guess what? The store that looked at my dead battery like it was from Mars has two of them on their shelf.
I admit now that it was foolish of me to bring a sample of what I wanted into a Radio Shack store, put it into the hand of a Radio Shack employee and hope that I would walk out with a new one. What on Mars was I thinking?
I was happy to discover that the Radio Shack website offers free shipping.