No it doesn't work with SHARED, as I already said, it's not on cluster.
ORA12545 is still appeard randomly using SHARED and DEDICATED.
Then it sounds like a port and firewall issue.
Simply put, client connects on port 1234 to service. Service hands off the client connection an (existing or newly created) server process. The hand off cannot pass the socket used to accept the client connection, from service to server process. This means that the server process cannot communicate with the client. In this case server process and client (via service) negotiates a new port number to communicate on. This port number is in the private/dynamic port range (blocked by default by firewalls). It requires a reconnection between client and server process. (read up on active/passive FTP that explains this issue technically)
The dispatcher processes listen on dynamic ports. They handle shared server connections request. Old style Oracle client-server saw the listener redirect the client to connect to the dispatcher's port - as oppose to new style where the listener passes the socket handle to the dispatcher and it continues the conversation with the client.
So from what you describe, it sounds like you have an old style (not sure what else to call this) behaviour - and with the firewall not allowing client and server to negotiate a new connection between them using a dynamic port.
SQL*Net tracing on the client should be used to troubleshoot, and confirm/reject this as happening.