"Without a trace" is the normal phrasing—compare the two on Google. :-p

No worries on the expensive part. I didn't check to see if that fit in the character limit.

--Ed