I have having some weird things happen with my contacts. Sometime I will enter a new contact and it WON'T show up in my contacts list on the Droid, but it WILL show up on my contacts in gmail.
So what I did was cleaned up my gmail account and made sure to sync my contacts on the Droid. Now the contact shows up in the contacts list on the Droid, but not when starting a new text message.
EXAMPLE - I go to create a new text message and start typing the name LANCE. I have a Lance L and a Lance E. After I type out L-A-N-C-E, only Lance E shows up under the messaging contacts. In order to send a text to Lance L, I need to just go to contacts, push and hold on his name, and select "Text Contact."
And yes, I do have the name spelled right! Let me know if you have any questions.