Was lactose present in the environment before the evolution of mammals?
Preamble

This is an answer to the motivation expressed in the question:


  “…whether lactose-utilising enzymes in bacteria evolved only after the appearance of mammals”


rather than that in the title. The presence or absence of lactose elsewhere in Nature will not decide this question.

Answer

The name lactase is applied to the mammalian enzyme that is able to catalyse the hydrolysis of the disaccharide, lactose, to glucose and galactose, allowing the digestion of this milk sugar by the suckling infant. However bacterial and plant enzymes that are normally referred to as β-galactosidases can also catalyse the same reaction. 

The role of the β-galactosidases in bacteria such as Lactobacillus lactis that are found in a dairy environment may well be to hydrolyse milk lactose, as may be that of Escherichia coli, found in the human gut. However this is unlikely to be generally true for all bacteria. This is because β-galactosidases are found in a wide spectrum of bacteria, including extremophiles† which cannot possibly have had access to milk lactose. 

β-galactosidases are generally members of a group of enzymes termed glycoside hydrolases and have been categorized into a number of families on the basis of sequence similarity. The enzymes in these families differ in their substrate specificity. To explain the existence of such enzymes in bacteria which do not have access to lactase it has been suggested that their natural substrates may be other disaccharides. This is actually the subject of a PhD Thesis by S.A. Shipkowski, who suggests that some β-galactosidases may actually hydrolyse β-1,4 galactobiose:



The significance of this is that the polysaccharide, pectin, found in certain plant cell walls, could be broken down by by other enzymes in the bacteria, yielding galactobiose.

Conclusion

Although the β-galactosidase in certain bacteria may be optimized to hydrolyse milk lactose, the gene encoding it is almost certainly derived from an ancestral glycoside hydrolases gene, the product of which predated the appearance of mammals and was used to hydrolyse other disaccharides derived from polysaccharides originating from various sources.

† It should be emphasized that the β-galactosidase from extreme thermophiles such as Thermus thermophilus KNOUC114 — isolated from a hot spring — hydrolyses lactose well. Indeed, its thermostablity has attracted interest in its development for use in the food industry (Ahn et al. 2012).