環境は

こういう場合は、プログラムを小さくして調べたらいいでしょう。

たとえば

Dim xlApplication As Excel.Application

Try
    xlApplication = New Excel.Application
    If Not xlApplication Is Nothing Then
        Try
            xlApplication.Quit()
        Finally
            System.Runtime.InteropServices.Marshal.ReleaseComObject(xlApplication)
        End Try
    End If
End Try

というように 最小単位から ちゃんと終了するのか 確認していけばいいです。

私は

If Not xlApplication Is Nothing Then

と 判断している個所が あやしいような気がしますが。

COMオブジェクトの解放忘れの項目が該当？

http://hanatyan.sakura.ne.jp/dotnet/Excel08.htm