There are various reasons why a vehicle may be a total loss, and these can vary from state to state. Obviously what was wrong with it has a big bearing on how skeptical one should be of the rebuilt/salvage title. Often this information is not readily available; sometimes it is.
There are some states and situations where a stolen vehicle is declared a total loss and ends up with a salvage title even if it is later recovered with minimal or no damage. On the other side of the scale, flood damage or major structural damage from a crash or other such things can cause it to be totaled and be impractical to repair properly and economically. I would guess that the latter cases are more common...but I don't really know.