There are actually two questions to resolve here: (1) What is the appropriate capitalization of the name/phrase "Rudolph the Red-nosed Reindeer" in the body of the poem or song of that name? (2) What is the most sensible way to refer in a one-off written allusion to the character Rudolph who is a red-nosed reindeer?
Should 'the red-nosed reindeer' be initial-capped within the poem?
If Rudolph's surname were "Reindeer" and his full name were "Rudolph the Red-nosed Reindeer"—similarly to "Anne Elk" or "Bullwinkle J. Moose," you would certainly expect all of the major words in his name to be initial-capped, regardless of where the name appeared.
However, if "the red-nosed reindeer" is merely a description by which Rudolph (no specified surname) is familiarly known, his case is no different from that of Tom, the piper's son, in the nursery rhyme "Tom, Tom, the Piper's Son," about whom it is reported:
Tom, Tom, the piper's son, / Stole a pig, and away did run; / The pig was eat / And Tom was beat, / And Tom went crying / Down the street.
Whether the little thief's proper name was Tom Piperson or something else, he was identified within the nursery rhyme as "Tom, Tom the piper's son"—a description that falls short of being a cognomen, but instead rates as a given name plus a simple descriptive phrase. Consequently, Wikipedia very properly (in my opinion) lowercased "the piper's son" in the first line of the ditty.
I don't know whether Robert May, who wrote the original book Rudolph the Red-nosed Reindeer in 1939, used the initial-cap form "Rudolph the Red-Nosed Reindeer" in the lines of his poem, or whether that change occurred in the libretto of the song "Rudolph, the Red-nosed Reindeer" by Johnny Marks in 1949, or whether it originated in the idiosyncratic orthographic choices of later third parties. But it would certainly have posed no challenge to story coherence or character recognition within the book if May had lowercased "the red-nosed reindeer" throughout.
Should 'the red-nosed reindeer' be initial-capped in incidental allusions to Rudolph?
It seems worth mentioning that all of the other reindeer in the story and song are identified by single names: it's Dasher, Dancer, Prancer, Vixen, etc., not Dasher the Reckless Reindeer, Dancer the Rhumba Reindeer, Prancer the Frolicsome Reindeer, and Vixen the Reindeer Fatale. So within the original book, it seems likely that Rudolph's entire name was Rudolph and that "the red-nosed reindeer" was a descriptive phrase, not part of a formal cognomen along the lines of "Eric the Red" or "Norbert the Nose."
In the real world outside Robert May's original book and Johnny Marks's original song, however, we run into the problem that there are a lot of Rudolphs (and Rudolfs) and very few widely recognized reindeer with given names—Rudolph the Silent Heartthrob, for example, and Rudolf the Flying Russian, and of course Rudolph Bald-Faced Lawyer. As a result, there are relatively few occasions on which the point of identifying Rudolph as "the red-nosed reindeer" is to distinguish him from other reindeer that might otherwise come to mind. Instead, the full expression usually arises in the context of instances where people want to refer to the now-familiar character Rudolph (who happens to be a reindeer with a red nose) in a way that immediately distinguishes him from other prominent Rudolphs.
In this way—by the backdoor to the stable, as it were—"Rudolph the Red-Nosed Reindeer" becomes a useful and semi-official cognomen for this particular fictional character, regardless of how May and Marks may have imagined the designation "red-nosed reindeer" originally. And under these circumstances, I think it is sensible to consistently initial-cap the R's in "Red-nosed" and "Reindeer" in passing references to the cervine Rudolph with the rosy schnoz. (Capitalizing the N in "Nosed" is less crucial and involves specialized considerations related to the capitalization of compound modifiers in titles. Suffice it to say that agreement on this point as a matter of title-case style is not universal.)
