That seems like quite a bit of deviation from -12v. The most I have seen from any power supply (desktop or dc-dc). But you are correct that they dont need to be as regulated as the + lines, because they are not used as often in the system.
And the problem you say is random. Is it really really completely random, or can you find a correlation between if or how fast you are moving, the type of road you are on such as bumpy and potholes to smooth, to if it happens on onramps when accelerating or when braking fast, or when it is cold/warm/humid outside, anything like that? Or is it really just random?