Nick,
With the latest dog we ended up using (over my strenuous objection) one of the "zappers." It's like the "invisible fence" but it's triggered by a remote control instead. Dog bites you, he gets shocked. It'll take about two times before he gets it.
As much as I hated it, I can't argue with the results and it's been good for him in the long run. Combined with other methods (and the other methods first and foremost), he's now trained to not go into the street (or onto any pavement) by himself and that sort of thing unless he's "heeling" with a human. Now, we don't need a leash to take him for a walk - Out the "gate" (the only place he's allowed to exit from the yard, and only with a person) and start walking down the street. He'll run around some on his own, but when he comes to the next crossing street he'll sit, wait for me to catch up, walk across the street with me, and then take off, chase rabbits, etc. It lets him just be a dog for the most part, and keeps him safe too.
Whatever you do, best of luck to you both.