2009 HMMT November Guts Round Problem 10

Admiral Ackbar needs to send a 5-character message through hyperspace to the Rebels. Each character is a lowercase letter, and the same letter may appear more than once in a message. When the message is beamed through hyperspace, the characters come out in a random order. Ackbar chooses his message so that the Rebels have at least a \frac{1}{2} chance of getting the same message he sent. How many distinct messages could he send?

Answers are checked by value, so any equivalent form is accepted: 1/2, \frac{1}{2} and 0.5 all count as the same answer.

Full credit goes to HMMT for authoring these problems. This problem is from the November 2009 contest; the official solution is available on the HMMT archive. HMMT is not affiliated with or endorsing TopsOJ in any way.