I would place the new column table in the same workbook (in a separate
sheet) as the original table, in case you haven't done that. Rather
than a vlookup into a separate workbook (in case you are using
separate workbooks).

If you are already running from the same workbook, then are you using
the false or true vlookup switch? In my experience if I use the false
switch (=vlookup(somedata,mytable,3,false) to find an exact match, it
runs faster with large tables.

Maybe try sorting the original and vlookup tables first. Maybe that
will help.

You might also want to try the merge in Access, using SQL statements,
if all else fails.