I've had similar problems when importing data from non-Excel sources.

I don't think the problem is formatting. That just dresses up the look
of the item, it doesn't actually change the data. Try this...

In a blank cell, type the number 1. Copy it to the clip board. Now
highlight all of your other data and from the menu select Edit Paste
Special Multiply. This will have the effect of multiplying
everything by 1. The numbers won't change and though the alphanumerics
look like they don't change, something happens that allows the vlookups
to work.

Not sure why, but that usually does the trick.

- John