What does message_body in sys.transmission_queue say?

Have you checked that routes are set up correctly on both servers? Make sure that service names (case sensitive), broker id and server names+ports are correct. Can you telnet the remote server + port from both servers? Try running a trace (including all broker events) on both servers to see if there is any communication between them. Any firewall blocking the ports you are using?