Hi,
I can't replicate your problem, I tested with some dummy data with 8000 characters in the cells, and used VLOOKUP, the results returned correctly, there's something else causing your incorrect results.
Can't help unless you post a link to a sample file here from a free file hosting site like Dropbox.
@MUKESHY, the 255 character limit is the Column Width limit, maximum number of characters within a single cell is 32,767