Sure but the caller network bills the telemarketer and they could be in cahoots.

Well yeah but that applies to local calls too and no telemarketer will sign up with a provider more expensive than they need.

Yes, but the premise here is that for national calls it becomes harder to spoof the caller id. In fact, here in Italy we're seeing an increase in telemarketing calls from Spain and France, so it's not entirely hypothetical.