We investigate the relation between Forbush cosmic ray decrease recovery time and coronal mass ejection transit time between the Sun and Earth. We identify 17 Forbush decreases from ground-based neutron count rates between 1978 and 2003 that occur during the same phase in the solar cycle and can be associated with single coronal mass ejections (CMEs) in the SOHO LASCO CME Catalog or previously published reports and with specific interplanetary coronal mass ejections (ICMEs) crossing the vicinity of Earth. We find an anticorrelation between Forbush recovery times and CME transit time that contradicts the predictions of simple cosmic ray diffusive barrier models. The anticorrelation suggests that the decay rate of ICMEs is anticorrelated with their travel speed. Forbush recovery times range from seven times the transit time for the fastest disturbance to a fifth the Sun-Earth transit time for the slowest. To account for the large range of measured recovery times, we infer that the slowest disturbances must decay rapidly with radius, whereas the fastest ones must remain strong. The longest recovery times suggest that the fastest disturbances in our sample decayed less rapidly with radius than the ambient solar wind magnetic field strength.