Check out your cheapie stores for some netting. Lay it on the lawn and when you want to use the lawn just peel it back. It won't hardly be noticed. The cats will soon learn and after a few months you might be able to remove it for good.
For borders I just *planted* kebab sicks, with the point sticking out of the ground, no more cat parcels ;D
(http://i201.photobucket.com/albums/aa42/ElleEss_photos/RaisedBed.jpg)