I am not sure if you loose prestige when you loose control of a province, I was offering that as a possible explanation. Are you playing this in vanilla EU3? The spy bug is easy to fix in the data files, if it's fixed for you, then you would loose prestige when discovered. Did you get many rejections when offering royal marriages? That is the single most damaging event for prestige.