In this paper, we present a novel methodology for improving the performance and dependability of application-level messaging in Grid systems. Based on the Network Weather Service, our system uses non-parametric statistical forecasts of request-response times to automatically determine message timeouts. By choosing a timeout based on predicted network performance, the methodology improves application and Grid service performance as extraneous and overly-long timeouts are avoided. We describe the technique, the additional execution and programming overhead it introduces, and demonstrate the effectiveness using a wide-area test application.