We consider cross-section regression models for country-pair data, such as gravity models for trade volume between countries or models of exchange rate volatility, allowing for the presence of country-specific errors. This induces clustered errors in a nonstandard setting. OLS standard errors that ignore this clustering are greatly underestimated. Under the assumption of random country-specific effects we provide analytical results that permit more efficient GLS estimation even in settings where the number of unique country-pairs is very large. We include applications to international data on real exchange rates and on bilateral trade that provided the motivation for this paper. The results are more generally applicable to regression with paired data.