I believe you're right, and it's a voltage spike that's destroying your relays. A motor is an inductive load. One of the characteristics of inductance is that it will resist a change in current. In other words, if current is flowing through the motor when the relay opens, the motor windings will try to keep current flowing through the (now-open) circuit. This causes arcing and fouling in the relay contacts, which is likely why your relays are failing.
A fusing system won't help you in diagnosing the problem, because they only pop with excessive current (not voltage).
There are two ways for you to go:
1) (easy) Find a relay made for inductive (motor) loads. Look at their spec sheets. Generally, if the relay is rated for inductive loads, it will either say "Inductive" in the contact ratings, or will have an HP (horsepower) rating. An HP rating implies a motor load, which implies inductance.
2) ("fun") Add an MOV (metal-oxide varister) across the relay contacts. It acts kind of like a pressure relief valve. To make it even better, you could add an MOV and an RC snubber, which would make the power very clean.
As an example of relay ratings, look at this one from Schneider Electric. (You'll want to choose your own, tailored to your motor power ratings, etc...)
In the specifications, they show different ratings:

In this case, the one that you're interested in is the Horsepower rating. This relay can safely switch current to a 1-HP motor at 250VAC (or 0.5-HP at 120VAC).
I expect choice #1 will work just fine. If you choose to add an MOV / RC snubber, let us know, and we'll show you how to spec the parts. It's 3 parts at the most, so is not difficult to assemble...
Good luck!