Yes, the private investigation service you used to lookup the SSN would have your payment trail, unless you used a prepaid visa. But how does that help?

All the target knows is, his phone has been forwarded and his Gmail password changed. Even assuming the police are willing to help (which is unlikely), all they'll discover is that your phone number is forwarding to a disposable cell phone which was bought with cash.

Wouldn't the police be able to see that a PI service looked up the person's social security number?

No. The services maintain their own databases, and don't disclose their access logs.