Ever had a melody in your head and you just couldn't figure out what song it was from? If so, how about a music search engine? Basically just like Google, but instead of letters you enter the melody you have in your head - rhythm doesn't matter. If no matching array of notes could be found, there would be the obligatory "Did you mean..." phrase with a slightly altered melody suggested. Since most songs are made of various layers of instruments, you could have an advanced search and maybe select the type of instrument you know the melody of (voice being also an "instrument" in this case). It should also work for percussion, but that should be a separate option. Maybe instead of piano keys you could see a set of drums to input whatever you have in mind.
Interestingly, such a search engine could be used to make melodies that are more or less new by finding combinations of notes that haven't been stored in the database yet. Even more interestingly, you could finally find all the similarities in a large collection of songs. With another added function you could search purposely for songs that use similar melodies to the one given, sorted by relevance.
There could be more options, such as to search for harmonies, for a specific rhythms, accords, and maybe even popularity or complexity of melodies.
A quick search through the internet has shown me that there are already people implementing that idea, such as Melody Hound or Musipedia. There's even already some kind of patent that describes the process in detail. Also, Wikipedia shows an article about the Query by Humming method. Song Tapper lets you search a song by tapping the space bar to the melody in your head - a very interesting and intuitive solution, making it accessible to people who don't have the knowledge of playing the piano or the talent to sing a (more or less) exact tone.
Further investigation led me to a research document called "Query by Humming: How good can it get?", which basically describes the experiment of how a QBH system performs against simple human listeners. Unfortunately I couldn't find out when this document was published. But the research's result was that QBH has still a long way to go.
The QBH entry on Wikipedia led me to sloud, a website offering the QBH solution for implementation in other projects. It is however limited to singing "DA-DA-DA" and, according to the website, the search results "depend on your ability to sing". Their list of potential applications suggests the idea that you could create a contest for your music store: The better your customers sing their favorite tune, the higher the chances of getting a discount for that song (or maybe for the CD the song's featured on). They mention that this technology will draw instant attention to your online music store. And last but not least they add that this search by voice technology is part of MPEG-7, apparently the standard for description and search of audio and visual content.
Searching for melodies is still more or less in its infancy. Though I guess that in the next few years Amazon will have a Query by Humming feature and they will tell you to have a listen to songs which people bought who also hummed that tune.