In the search for highly efficient magnetic resonance imaging contrast agents, polyaminopolypyridinecarboxylate complexes of Gd3+ have shown unusual properties with both very rapid and very slow electron spin relaxation in solution observed by electron paramagnetic resonance. Since the relationship between the molecular structure and the electron spin properties remains quite obscure at this point, detailed studies of such complexes may offer useful clues for the design of Gd3+ compounds with tailored electronic features. Furthermore, the availability of very high frequency EPR spectrometers based on quasi-optical components provides us with an opportunity to test the existing relaxation theories at increasingly high magnetic fields and observation frequencies. We present a detailed EPR study of two gadolinium polyaminopolypyridinecarboxylate complexes, [Gd(tpaen)]- and [Gd(bpatcn)(H2O)], in liquid aqueous solutions at multiple temperatures and frequencies between 9.5 and 325 GHz. We analyze the results using the model of random zero-field splitting modulations through Brownian rotation and molecular deformations. We consider the effect of concentration on the line width, as well as the possible existence of an additional g-tensor modulation relaxation mechanism and its possible impact on future experiments. We use 17O-NMR to characterize the water exchange rate on [Gd(bpatcn)(H2O)], and find it to be slow (~ 0.6x10^6 s-1).