I've spent the last hours to go over the articles of that
site but none could help me.
In fact the article which raises the problem would be the
best answer to my question
(http://msdn.microsoft.com/library/default.asp?
url=/library/en-us/dnout2k2/html/odc_oladdinvbnet.asp)

Let me explain what I've tried in more details.

From the article:

Working with a Setup Project
You've learned about the critical working code of an
Outlook add-in built with Visual Basic .NET. Accompanying
the sample OutlookCOMAddinVBNET project is the setup
project named OutlookCOMAddinVBNETSetup. There are several
important setup issues that you must address when you
deploy an add-in developed with Visual Basic .NET:

* You must install the Microsoft .NET Framework
(approximately 20 MB) on the target machine before you
install your add-in.

Okay, I did this, no big deal.
(If the .NET Framework is not installed the setup will
tell you)

* You must install the Outlook Primary Interop Assembly on
the target machine. See the "To Use the Outlook 2002 PIA
in Your Solution" section above.

Im pretty sure that this is also done. The needed pia dll
is added to the setup project and I've even test the pia
with something like this:
Module Module1
   Sub Main()
       'Purpose: Test the Microsoft Outlook 2002 primary
       'interop assembly (PIA)
       Dim olApp As New
Microsoft.Office.Interop.Outlook.Application

       Console.WriteLine("The version of Microsoft
Outlook installed " & _
           "on this computer is " & olApp.Version() & ".")
       Console.ReadLine()
   End Sub
End Module

So, this should be also okay.

* If your Setup project installs the add-in registry keys
under HKEY_LOCAL_MACHINE (HKLM) instead of
HKEY_CURRENT_USER (HKCU), the add-in will not be visible
in the Outlook COM Add-ins dialog box.

I understand this but since everything is already in its
place I dont need to worry about this, right?
Also I've already checked the registry and the 3 necessary
keys are in their places.

So, I dont see a mistake here too.

* The COM Add-ins dialog box will display the common
language runtime engine, mscoree.dll, as the source of
your add-in instead of the name of your managed code add-
in as shown in Figure 7. In the case of the sample
application, the actual file name is
OutlookCOMAddinVBNET.dll.

As I stated in my first post, the COM Add-in is shown in
the COM Add-ins dialog box but its not checked because:
"Not loaded. A runtime error ocurred during the loading of
the COM add-in."

So everything is alright, isn't it?

Okay, lets continue

Required Setup Distributions
*snip* (see article, would be too long)

Note   In the sample OutlookCOMAddinVBNETSetup project,
all these steps have been completed for you. Be aware that
the OutlookCOMAddinVBNET Setup project, in order to
minimize download size, does not include Windows Installer
Bootstrap files.

Thats the important part, ALL these (snipped) steps should
have been completed for me.
The only thing about which I'm unsure is the not included
Windows Installer Bootstrap files. Don't know which impact
that has.

So in sum of all this, I did everything the solution
needed me to do but its still not working.
I've even set the Macro Security to Medium, I wasn't sure
whether outlook just blocks the addin and causes such an
error as stated above.

I don't know what went wrong, thats why I'm here.
Any helpful ideas are welcome.
I even don't know how to track the problem (more) down.

Kinda regards,
Mat.

Okay,

its me again.
I researched and debugged a little more and figured the
following out.
Thats the OnConnection procedure Im using (should be the
same as provided by Randy Byrne)

Public Sub OnConnection(ByVal application As Object, _
           ByVal connectMode As
Extensibility.ext_ConnectMode, _
           ByVal addInInst As Object, ByRef custom As
System.Array) _
           Implements
Extensibility.IDTExtensibility2.OnConnection

       Dim oApp As Outlook.Application
       Dim oType As Type
       Dim GetProgID As Object
       Dim MyProgID As String
       Dim oArgs As Object()

       Try
           'Use InvokeMember to get the ProgID of
addInInst object
           oType = addInInst.GetType
           GetProgID = oType.InvokeMember("ProgID", _
           BindingFlags.Public Or BindingFlags.GetField _
           Or BindingFlags.GetProperty, _
           Nothing, _
           addInInst, _
           oArgs)
           MyProgID = CType(GetProgID, String)

           'Convert application from generic object to
           'Outlook.Application.
           oApp = CType(application, Outlook.Application)
           'Don't call InitHandler if Explorers.Count = 0
and Inspectors.Count = 0
           If oApp.Explorers.Count = 0 And
oApp.Inspectors.Count = 0 Then
               Exit Sub
           End If
           'Evaluate ConnectMode
           Select Case connectMode
               Case ext_ConnectMode.ext_cm_AfterStartup
               Case ext_ConnectMode.ext_cm_CommandLine
               Case ext_ConnectMode.ext_cm_External
               Case ext_ConnectMode.ext_cm_Solution
               Case ext_ConnectMode.ext_cm_Startup
               Case ext_ConnectMode.ext_cm_UISetup
           End Select
           ' Initialize COMAddin object with this connect
object to allow
           ' external clients to get access to exposed
features
            oApp.COMAddIns.Item(MyProgID.ToString
()).Object = Me 'problem here
           'Call InitHandler
           m_BaseClass.InitHandler(oApp, MyProgID)
       Catch ex As SystemException
           DebugWriter("OnConnection Exception: ",
ex.Message)
       End Try
   End Sub

Okay, when I comment the "oApp.COMAddIns.Item
(MyProgID.ToString()).Object = Me" the add-in will
actually load into outlook (remember this all only
happens, when im installing the add-in on another machine)

Unfortunatly, I can't call the inithandler:
OnConnection Exception: File or assembly name office, or
none of its depencies, was not found.

Are they somehow related to each other?
Or did I miss more than one thing?

Any help would be appreciated.
Thank you in advance,
Mat.