I think spies are just fine to keep your provences happy. Later in the game (passed the 60% mark) you need spies or you are going to have more rebellions then you can deal with. That alone makes them worth the money. Plue you can have a group of spies follow your army stacks. That way you can move stacks out of a newly taken provence quicker.