Telco logs are another place to start - many dodgy cold callers might be able to spoof the caller ID, few are clever enough to actually disguise their tracks any better.
Caller ID (technically called CLIP: Calling Line Identification Presentation) is a number presented by the end user. It's not so much of a case as "spoofing" it, but just supplying something inaccurate.
Your supplying network knows who's called and from which network: they just pull their billing information which is rather more complete than what you get on a handset.