This paper describes the difficult problem of seamless messaging in heterogeneous communication environments and the design of cooperative agents to address the problem. The seamless messaging agents include coarse-grained agents such as user agents, message transfer agents, server agents (for resources such as speech recognition and generation), application agents (interfacing to mail applications such as Microsoft and Unix mail) and device agents (for wireless phones, laptops, etc.). It also includes fine-grained agents, namely, user surrogate agents. Seamless messaging requires real-time performance which necessitates a tradeoff between agent communication, adaptability and intelligence to achieve a variety of tasks. In addition, seamless messaging requires user interface mediation between users and device agents to allow, for example, messages sent by users from a powerful graphic workstation to be received transparently by a cellular phone.