I had similar issues but only with hostile mobs (sheep, wolves, chickens, cows were not an issues), and noted the following:
1. Exported the map into MCEdit, I saw that there were a significant number of spawns in a square pattern around the spawn point. The area was approximately 10x10. These spawns were above the ground, yet not visible to me when i was in that area. I deleted the chunks, loaded the map and all was well, for a time. Then the problem reoccurred. Spawns would be good for a day or so, then start to degrade.
2. The problem stopped when I upgraded my CPU in the dedicated server. I went from a Q6600 (Quad 2.4) with 8GB ram to an i7 with 16GB of ram. I have had no issues since then with mobs spawning.
I can only surmise that since my old CPU could not handle the load (avg of 75ms/t), the poor system performance was a factor in the issue.