Your question is very reasonable and I remember to have read an article about p2p foundamentals where it was mentioned as one of the practical problems for p2p network applications. I am not familiar with how exactly this kind of services work, but the key is that we are talking about centralized p2p model where we rely on a central node to coordinate the connections between the peers. So practically, the server has both of the clients open outgoing connections to each other's same port, so as to allow bidirectional connection even in peers where NAT is applied.
I was under impression that if we're trying to request a service running on port 23 (which is telnet), then our source ip for this request would also have to be 23
The tcp handshaking procedure defines that a non-privileged port (1024 and above) would have to be used for the outgoing connection. This is for flexibility (so that there can be more than one connection to the same destination port) and for security (if ports for outgoing connections are picked in a -even slightly- random way it is more difficult and time consuming for a third party to guess and do whatever). It is of course possible for the programmer of an application to define the source port (usually a range as the application could commonly need to open more than one connection).
then two P2P application running at the same time on different pcs behind the same router/NAT device should work without a problem, so we wouldn't need to map a second ip to a second local ip in order for this to work. Correct?
I am sure that is correct, though I haven't tested it in practice