How can I find out how many versions of a specific song have been recorded?

When I read your question, all I could think of was Frank Sinatra's signature version of this song, but then I realized that I have a couple of versions of this song in my own iTunes library, actually, including a great version from Ella Fitzgerald and a version by Nat King Cole too. So maybe there are more than a hundred covers of Fly Me to the Moon recorded.

Just as the Internet Movie Database can settle lots of questions about movies and TV, though, it turns out that the CD Database (now known as "Gracenote") can settle lots of these sort of these sort of questions for music.

If you're thinking that "cddb" sounds familiar, it should, because it's the site that music players check to get album, artist and track information when you rip a music CD, whether you're in Windows Media Player or Apple iTunes. Turns out, it has an astonishing database of music and CD information now, 5,365,466 CDs representing 68,646,864 songs.

To answer your question, you'll want to go to the Music Search area, which shows you the following options:

All you have to do at this point is type in the name of the song, click "exact match" and click "Search". A second or two later the surprising answer to your question is revealed:

Almost 1800 CDs in the Gracenote library have a version of Fly Me to the Moon, so your friend is most assuredly correct, even if you factor out multiple CDs from the same artist.

So now you know, and I can't say how interesting it is to poke around on Gracenote looking at things like how many CDs have the word "banana" in the title (232) or how many artists are named "Dave" (4935 matching CDs) and similar. Cool site, well worth a bookmark.