"frozen ice machine" gets 92,800 ghits.
The thing I find interesting about pleonasmata is how popular they are and why. Of course, the folks who disparage them and their use are upset, but most of the language-speaking world is blithe to their existence. But redundancy is not something bad in language. In fact, there are many instances of redundancy that don't set the normative grammarians off like a cheap fourth of July firecracker. Concord between different constituents in a sentence is something that is good and grammatical and must-needs be upheld.
And other languages display it to a greater extent than English. Adjectives in Russian, German, and Latin have to agree with the noun they qualify in number, gender, and case. This bluntly put is pleonasm. The information is thus encoded lover several words. Of course, there is a benefit to this, especially in the case case: i.e., it's easier to move words around in a sentence or phrase. For example, in English the nature of things and the things of nature have two different meanings, but in Latin de rerum natura and de natura rerum can only mean the 'nature of things'. In fact, this sample phrase illustrates how Latin is capable of splitting prepositional phrases without the risk of unmeaning.
