What kind of phone is it? Windows based/Java/Blackberry/Treo OS?

As for the phone company being able to trace it..if it's done through bluetooth they wouldn't have any record of it.