Computer Vision
Clearly the best solution for navigation would be the some of the normal motion analysis/structure from motion computer vision techniques, for automated guidance.
Simply mount a standard vga webcam, streaming to a box in the house with a big processor. Build some software based on Open CV that is capable of identifying grass texture and distinguishing it from, say, flowerbed. It would then be track garden landmarks, flowerbeds, fences etc. to work out where it was on the lawn.
On the first haphazard pass it would build up a picture of the lawn until it had the whole lot, and after that it could calculate the most optimal route.
The software would be quite involved, but it would keep the part cost for the machine down as all, particularly if you are using an existing computer for processing resource. Processing could be put in the mower, keeping it as a fully independent, autonomous sheep/goat.
Non-obvious boundaries could be input on an interactive map, or indicated using some form of easily computer recognisable marker, e.g. QR code as someone suggested.
What I'm envisaging is a single hardware platform (designed using some of the excellent ideas above, and presumably below) on which a multitude of people are developing open source cleverness to turn it into a mower.