Windows8・VB.NET(Visual Basic 2010)とOffice2013がインストールされているPCで質問です。この環境でサムネイル含むListViewの内容をExcelオートメーションクライアント/Excel.ShapesのAddPicture等を用いて書き出すプログラムを作ったのですが、完成したプログラムをOffice2007/2010がインストールされている別のPCでも実行できるようにする方法を教えてください。

遅延バインディングの場合は、Excelの参照設定を解除して、自前で定数宣言をする必要があります。
MsoTriState であれば

■ MsoTriState 列挙 (Office)
http://msdn.microsoft.com/ja-jp/library/office/ff860737.aspx

を定義します。

以下、遅延バインディングのサンプルです。

Public Class Form1
    Public Enum MsoTriState
        msoFalse = 0
        msoTrue = -1
    End Enum

    Private Sub Button1_Click(sender As System.Object, e As System.EventArgs) Handles Button1.Click
        Dim excel = CreateObject("Excel.Application")
        excel.Visible = True
        Dim book = excel.WorkBooks.Add
        Dim sheet = book.ActiveSheet
        Dim strFileName = "C:\home\edu\vs2010\vb\ExcelAutomation\xyz.png"
        sheet.Shapes.AddPicture(strFileName, MsoTriState.msoFalse, MsoTriState.msoTrue, 0, 0, 100, 100)
    End Sub
End Class

エラーが出るのは、やはり、参照設定が残っている為と思われます。

以下の何れかのツールを用いて「Microsoft.Office.Interop.Excel」が設定されていないことを確認してみてください。
設定されている場合、参照設定がまだ残っていると思われます。
・ildasm（http://msdn.microsoft.com/ja-jp/library/f7dy01k1.aspx）
・ILSpy（http://ilspy.net/）