Lewis and Short glosses fessus as:
wearied, tired, fatigued; worn out, weak, feeble, infirm
It lists defessus (which is the past participle of dēfĕtiscor as a synonym. It has a similar meaning:
to become tired or wearied; to grow weary, faint; to be exhausted
So far, this isn't helpful. Our breakthrough comes, though, when we realize that de- can function as an intensifying prefix, as in L&S II.2.c., which includes many examples:
With reference to the terminus of the action: defero, defigo, demitto, etc.; hence also trop., with reference to the extent of the action, to the uttermost, to exhaustion, throughout: debacchor, debello, dedolo, delino, delibuo, etc.: defatigo, delaboro, delasso, etc.; hence freq. a mere strengthening of the fundamental idea, = valde, thoroughly, much: demiror, demitigo, etc.
It is almost certainly in this sense that defessus indicates a more thorough exhaustion than fessus. This is confirmed by the Copious and Critical Latin-English Dictionary:
Defessus: entirely exhausted so as to be obliged to give up.
This aspect of "giving up" appears in other comparative works as well (such as here).
It's impossible to speak of rules, here, but the nuance appears to be something like the following:
Defessus sum quaeritando. --I am tired of looking [so I am stopping].
Fessus sum quaeritando. --I am tired of looking.
Some examples don't include this "stopping" nuance, in which case you are safe to assume that it just is intensitive, e.g. "I am very tired" or "I am exhausted."
Both forms are listed as frequent in classical Latin, though fessus is about five times more frequent. This is a difference between common and extremely common, and both are easily understood.