Do large animals often evolve into smaller animals?
Your question brings up several important issues with regards to the evolution of body size. The rationale for concluding that the ancestral mammal had a small body size is that all of the taxa in that area of the tree tend to be small. In contrast, if all of those taxa had been cow-sized, then the most parsimonious conclusion would be that the ancestral mammal was cow-sized.
Identification of ancestors is difficult
Identification of a fossil species as the most recent common ancestor of a pair of sister taxa is exceedingly difficult. The way that different species are diagnosed in fossils in by their unique derived characteristics (autapomorphies). So if a fossil is found with no autapomorphies, then it is plausibly an ancestor (i.e., at the split between two sister taxa). Some would argue that if you don't find any autapomorphies, then you just haven't looked closely enough.
Cope's Rule
The idea that lineages tend to evolve toward larger body size is known as Cope's Rule, named for the paleontologist Edward Drinker Cope. The success of Cope's Rule has been highly variable, with some lineages following and others not (Polly, 1998).
Some clades following Cope's Rule

Early reptiliomorphs (Laurin, 2004)
Pterodactyloidea (Hone and Benton, 2007)
Most Cambrian-Devonian marine invertebrates (Novack-Gottshall, 2008)
North American canids (Van Valkenburgh et al., 2004)
Mesozoic birds (Hone et al., 2008)

Some clades not following Cope's Rule

Early stegocephalians (Laurin, 2004)
&quot;Rhamphorhynchoid&quot; pterosaurs (Hone and Benton, 2007)
Mesozoic birds (Butler and Goswami, 2008)

Note that many results depend on the methods used.
Evidence from experimental evolution
Several studies have addressed body size evolution in vertebrates both directly and indirectly. MacArthur (1944a, 1944b) directly selected for large and small body mass in laboratory mice. Within 8 generations, mean body masses had increased or decreased by over 50%. Even when body mass is not directly selected upon, mass can change in a correlated way. Selection for high levels of voluntary activity has led to an approximately 25% reduction in body mass.
Based on these studies, evolution of body size (larger or smaller) is certainly possible within relatively few generations.