We describe the design and implementation of a "Grid-enabled" message passing library, in the context of the Phoenix message passing model. It supports: (1) message routing between nodes not directly reachable due to firewalls and/or NAT; (2) resource discovery facilitating ease of configuration that allows nodes without static names; (e.g., DHCP nodes) to participate in computation without specific efforts; and (3) nodes dynamically joining/leaving computation at runtime. We argue that, in future Grid environments, all of the above functions, not just routing across firewalls, will become important issues of Grid-enabled message passing systems including MPI. Unlike solutions commonly proposed by previous work on a Grid-enabled MPI, our system runs a distributed resource discovery and routing table construction algorithm, rather than assuming all such pieces of information are available in a static configuration file or alike. Experimental results using 400 nodes in three LAN indicate that our algorithm is able to dynamically discover participating peers, connect them to each other and calculate a routing table. The elapsed time of our algorithm is only approximately twice as long as that of offline route calculation that just connects nodes based on a fully given configuration.