Does a lie have to have intent to deceive?

I would say intent is irrelevant for the definition of "lie". Think of so-called "white lie". Suppose your boss gives you a present for your birthday, and he asks, "Do you like it?" If you are polite, you would say "Yes" even if you didn't like it. The "intent" in this case is to be polite or to express your appreciation for the gift.

Many restaurants claim things like "World's best pizza". It's a lie because they have done nothing to prove that they do indeed serve the best pizza in the whole world. Is there an intent to deceive? No, because we all know that claiming something to be "world's best" is a common expression; it is not interpreted literally.

Say, you come home really tired and you are not in a mood to talk to your spouse, so when your spouse asks, "What did you do today?", you reply, "I went to the moon." It's a lie but you have no intent to deceive because it is obvious that you didn't actually go to the moon. The intent is to say, "I don't feel like talking right now," or "Don't ask me boring questions."

If you say something that's not true and you know it's not true, you've told a lie. If you say something that's not true and you don't know it, you've told a falsehood.

I wholeheartedly agree with most of the points SM makes. However, in reference to the third paragraph of the comment, it seems to me that a statement used to distract or deceive may or may not be a lie. I think the most agreed-upon requisite of a lie is that its perpetrator believes his or her statement to be false. A person who makes a statement he believes to be true would probably not commonly be thought to be lying, even though he may be intentionally distracting someone from learning the facts of a matter. In that light, the child saying "Mommmy I love you." when asked about a mess he was caught making is employing duplicity and deceit, but I don't think he is lying. That is, unless he believes that he does not love his mother. A lie is only one of various forms of deceit.

I think it's helpful that our language helps us minutely differentiate various forms of deception. Widening the usage of "lie" to include any type of deception, whether or not it entails the statement of falsehood, hinders our ability to clearly describe deception in all its forms. (That's not to say that the development of language in any way "cares" what I think is helpful!)

If one speaks a lie, full of intent, and there is nary a tree about to hear it, is his soul darkened to any notice?

If I speak a lie, again full of intent, and my wife does not hear the words as they are spoken, and smiles delightfully while thanking me for the complement, is the frustration of the failed attempt a sufficient penance?

I agree, basically. A lie needs to be a deception. However, if lying to oneself is possible then how is telling others the same untruth not a lie?
After you've allowed yourself to be convinced then sharing that lie, believing in it, still would make one guilty of lying. It is because of how convinced you have become without sufficient evidence. Our assumptions make us liars.

I disagree with Dyske's answer.
In the first example, you are saying something that you know is not true.
In the second example, that is a subjective opinion. They can truly believe they have the best pizza, just like you hear people say they have the greatest wife or kids. It's a subjective opinion that they may truly believe in.
In the third example, that would be a lie because once again you are saying something that is not true even though it's hyperbole.
The way I under the definition of "lie" is that it wouldn't be a lie if I say something I BELIEVE to be true, but is factually wrong. If the police ask me to describe a suspect from memory I could truly believe I'm giving the correct description from memory and be factually wrong, but wasn't my INTENT to deceive the police.

What about the myriad falsehoods being spread on the internet? For example, "President Obama is a Muslim.", is a false statement. It was most likely started and propagated by people who wanted to smear his reputation, which would make it a lie for them, clearly. However, lots of Bible-believing Christians have repeated that lie. Is it correct to say that the statement is a lie even if the person repeating the lie actually believes it is true? In this day and age of trolls, are we culpable if we fail to verify "facts" before repeating them? So, if we repeat a lie without checking it, are we liars?