It is alot easier to lose rep than gain it. It annoys the heck out of me too because I always exectue prisoners (honestly, why would I let my enemy get his prisoners back?!?!) and exterminate cities (otherwise public order is too chaotic) and if you want a smooth game you really have to do those two things (at least imo).

So yeah, after about 25 turns my reputation is always despicable even though I make a point never to attack allies until I have cancelled alliance.