Early bound reference are "bound" (excuse the pun) to cause a problem on applications being distributed to users with different Excel versions.
Using late binding and coding for the earliest version of Excel you are willing to support is the solution. For example, if you were supporting Excel 2000, your application would only use methods supported in Excel 2000.
However, if your code was late bound, you could use ambiguous method calls and detect the local version to determine which code to run.
Ex:
Dim excelVersion As Long
Dim xl As Object
' get a reference to Excel.Application maybe from AddinInstance_OnConnection()?
excelVersion = Val(xl.Version)
Select Case excelVersion
Case 11 ' Excel 2003
' Excel 2003-only methods here
' ex: xl.FileSearch
Case 12 ' Excel 2007
' Excel 2007-only methods here
Case 14 ' Excel 2010
' Excel 2010-only methods here
' ex: something with Slicers
End Select
Since the code is late bound (i.e. derived from Object), I can specify methods that are valid only in Excel 2010 and the code will still compile. If the code was early bound to Excel 2003, it wouldn't compile. At runtime I determine the version to decide which methods to use.
You might also consider compiling different versions of your application, if you are using Excel 2010-specific features. Only you would know if that is possible.
Also, and I thought of this after writing this answer, but can't you reference Excel 2010 in your app, and if it is installed on computers with earlier versions of Excel, won't the reference automatically adjust to whatever version of Excel is installed?