I've the following network diagram:

Pr1<--->Pb1 <-------------> Pb2<---->Pr2

Pr1 is a host that only communicates with Pb1, and doesn't know nothing about Pb2 and Pr2.
Pr2 is a host that only communicates with Pb2, and doesn't know nothing about Pb1 and Pr1.

If Pr1 wants to send a message to Pr2, Pb1 must relay the message to Pb2.

What kind of service can I use to do this?

You might want to edit your post: don't know nothing -> doesn't know anything.

Your question is too abstract. What kind of messages? If host A knows nothing about host C, why does it want to send a message to C? What knowledge of the target doesn't it know?

If it is the IP address that isn't known and they are behind a NAT router, a third party server can be used that both hosts agree on. This allows the connection to remain open.

A broker could handle subscriptions to the messages. Such as multi casting, or perhaps for RSS, the Google reader service.
The message might be sent to everyone.

Pb1 is a gateway that hides the outside world to Pr1. The same for Pb2 and Pr2.

I found that one solution for all the hosts communicate is creating a VPN, for that, all private hosts can connect to each other. But can I connect all nodes with a routing table?