Depends on what you want as result, looking for identical matches one-to-one, Pauldes gave a good answer. I haven't used Vlookup too much but I write lots in VB. You can try this:
Sub Compare()
'Identify arrays
Dim aNoA() As String
Dim aNoB() As String
u = 1500 'Number of rows expected in Column A
v = 500 'Number of rows expected in Column B
ReDim aNoA(u) As String
ReDim aNoB(v) As String
'Set counters
h = 1
i = 1
'Fill arrays with data
For y = 1 To u
aNoA

= ThisWorkbook.Sheets(1).Cells(y, 1).Value
Next y
For x = 1 To v
aNoB(x) = ThisWorkbook.Sheets(1).Cells(x, 2).Value
Next x
'Compare short column to long (one-to-many searching)
For x = 1 To u
j = h
For y = 1 To v
'Find a match write it in Column C
If aNoA(x) = aNoB

Then
ThisWorkbook.Sheets(1).Cells(h, 3) = aNoB(x)
h = h + 1
End If
Next y
'When no matches write the number in Column D
If j = h Then
ThisWorkbook.Sheets(1).Cells(i, 4) = aNoB(x)
i = i + 1
End If
Next x
End Sub
Alex