I'm no cattle expert, so take my remarks in that context.
I'm inclined to recommend some sort of low-power, low-range transmitter which you could attach to each animal. For example, the JeeNode:
Judging by another page I found, you might expect a couple of hundred meters range, depending on terrain. This should be good enough for detecting if the cattle is in the paddock, or has wandered off or been stolen.
I would have each one sleep most of the time, and at some interval you determine wake up and transmit a short message to a base station. You could put a serial number (cattle ID) into the EEPROM of each chip, so each one sends a different code.
To save power, have a long time between messages, if you want to catch rustlers in the act, maybe a shorter time (eg. 15 minutes?).
The base station could be in the middle of the paddock (thus you get 200 m in each direction from the station, so you could have a 400 x 400 m paddock) and then base station could then repeat recent transmissions via (say) CB radio or a cell phone link.
Stuff about his measured power consumption here:
My own pages about saving power:
The simplest power source might be a button cell (eg. CR2032) which should last a year or two if you don't transmit too often. For example, my car keys use a CR2032 and I lock and unlock the car multiple times each day, and it lasts a few years.
As for the rustlers, if they leave the tag on the cow, then you have some hope of finding it. If they don't (and personally I would remove something as obvious as that) then you may find the gadget in the paddock, but not attached to Bessie any more. To try to stop that, you could have the wire that holds the tag to the cow register when it is cut. So they cut the wire, and the gadget then wakes up and transmits a "theft" signal. If they destroy the tag before cutting the wire, well you still get the "no cow" signal at the next appointed time (because it is not sending anything).
If they are smart and strip the insulation from the wire, and bridge the ends before cutting it (with a longer wire) then that scheme might fail. But you might also have a temperature sensor built into the device (a thermistor) which normally would register "cow body heat" but some other temperature if it has been removed. Another approach might be to have a light sensor on it. If the device is held against the cow's body then not much light would get in, if it is removed more light would get in (during the day, anyway).
At the same time, I want to build it into a sort of management system where farmers can track which cattle are in which area.
If you have multiple base stations (say half a km apart in each direction) then the one the animal is nearest to should register a signal, so you would have a rough idea of which cattle are where.