You will suffer a performance hit when using LINQ. Generally speaking, it is not that big of a deal but when you're working with that many values then yeah... it's noticeable. My first suggestion would be to see if you see an immediate relief when you use a For/Next loop instead. I've never worked with this namespace, but here is some pseudo code (that may or may not work):
Code:
'Get all of the entries
Dim entries As AddressEntries = .OutlookO.GetNamespace("MAPI").AddressLists(.AddressList).AddressEntries

'Create a list to store the entries that are AddressType
Dim addresses As New List(Of Outlook.AddressEntry)

'Placeholder variable for the entry
Dim entry As AddressEntry

'Iterate through the collection
For index As Integer = 0 To entries.Count - 1
    'Assign the value of the placeholder
    entry = DirectCast(entries.Item(index), Outlook.AddressEntry)

    'Check if it is an AddressType
    If entry.AddressEntryUserType = .AddressType
        'Add it to the collection
        address.Add(entry)
    End If
Next