Whenever I read the word randy (quoth the OED: “orig. Sc. and Eng. regional. Lustful; eager for sexual gratification; sexually aroused. [Now the usual sense.]”), my mind’s eye and ear instantly visualize Austin Powers in full leer: “Feeling randy? Fancy a shag?” Then I start visualizing Brits “‘avin’ a laff” about all the Americans with names like Randy Newman, Randy Travis, and Randy Moss.
This has been happening more and more lately, most recently last night as I was reading a Jonah Lehrer article in the New Yorker in which he mused about the odd behavior of male Australian gray-crowned babblers: “Instead of acting like randy juveniles, seeking out mates and getting into territorial fights, they are content to remain at home.”
But it’s not just The New Yorker, as witness:
“In the Mood,” a new song and a strong indication of where New Edition is likely to go next, was a randy, simmering seduction anthem. (Newark Star Ledger, February 21, 2012)
Seth [the Justin Theroux character in the film “Wanderlust”] suggests a cross between Charles Manson and a randy hobbit. (Boston Herald, February 23, 2011)
The only conceivable response is:
“Yeah, baby.”
notoneoffbritishisms.com 
.Old stuff. Heard and read this usage of randy back in the ’60s. Didn’t stop people from calling their kids Randy (or Randi or Randee).
I first heard this back in the 1960s, as well…men got horny and women got randy.
On a side note, circa 1990, I place a business call to a colleague in Germany. To the person who answered, I asked if so-and-so was handy (meaning was he available to talk), which evoked a refused-to-be-explained chuckle from the other end of the telephone line.
In Germany a mobile or cell phone is called a Handy – from Handfunktelefon.
Maybe this was the cause for the Teutonic mirth of your interlocutor.
Young man to attractive girl: “Are you randy?”
She: “No, I’m Sally.”
Old stuff but still good for a non-PC snigger
Yes, jokes about this have been around for a long time, so lots of Americans know about it. If the word is now creeping into American usage as well, it may be because it serves a purpose. It is less vulgar than “horny,” which is not a word most respectable publications would use. Is there an alternative to “horny” that works well in this type of setting?
“Lusty” has too many possible meanings, especially if the topic of the article is not sex. Other words, like “lubricious,” “concupiscent,” “libidinous,” et al. are all too formal, rare or prim. Off the top of my head, I can’t think of a word that has quite the same sly, slangy, naughty-but-not-too-vulgar sense that “randy” has in American English.
In this way, it resembles “to wank” for masturbate. You’ve already covered “wanker,” but it might be worth re-visiting “wank” in its literal sense. I think it’s becoming more common in America just because it’s short and blunt and yet less vulgar than “jerk off.” I don’t know whether it’s use has risen to the level of newspapers and the like, but Americans are using the expression in chat rooms and web forums pretty commonly now. Or, erm, so I’m told …
That would be “its use,” not “it’s use.” [This would be the place to insert an “oops” emoticon if such were available.]
The Newark Star Ledger hasn’t quite got it. “Randy” is a seaside postcard, tabloid kind of word, far removed from shimmering seduction (whatever that is).
Randy Baumgardner (the politician) has featured on TV over here as the ne plus ultra of silly American names. Randy California from the band Spirit also used to raise a few laughs on radio. When the Monkees released Randy Scouse Git as a single it had to be renamed “Alternate Title” for the British market (though the original title came from the British TV programme “Till Death Us Do Part”, later Americanized as “All in the Family”).
I still titter inwardly at the “shaggin’ wagon” mental image that was evoked by hearing the name of Randy Van Warmer on the radio (in the 1970s, in New Zealand).
In his youth Prince Andrew was referred to as ‘Randy Andy’ by British tabloids who covered his amorous affairs. Having Koo Stark, a former soft-porn actress, as a girlfriend helped to reinfornce the image. Here
is the 1984 ‘Randy Andy’ song from the puppet satire ‘Spitting Image’:
By all accounts his nephew appears to be carrying on the tradition.