Excel export without Interop

I don't know if this is the problem, it could. You do not Dispose the OleDbCommand objects. It's possible that it maintains a reference to the file. Try this:

Public Sub ExportDatasetToExcel(ByVal ds As DataSet, Optional ByVal strHeader As String = "Save As")

    'Proudly copied from:
    'http://www.daniweb.com/software-development/vbnet/threads/368400/write-into-excel-using-oledb-connection#post1583200

    Using fileSave As New SaveFileDialog()
        fileSave.Filter = "Excel 97-2003 Workbook (*.xls)|*.xls"
        fileSave.InitialDirectory = Environment.GetFolderPath(Environment.SpecialFolder.Desktop)
        fileSave.Title = strHeader

        If fileSave.ShowDialog() = Windows.Forms.DialogResult.OK Then
            Dim xlsFilePath As String = fileSave.FileName
            If xlsFilePath = "" Then Exit Sub

            System.IO.File.Copy(storagePath & "\" & "empty.xls", xlsFilePath)

            Cursor.Current = Cursors.WaitCursor

            Using conn As New OleDb.OleDbConnection(String.Format("provider=Microsoft.Jet.OLEDB.4.0; Data Source='{0}';" & "Extended Properties='Excel 8.0;HDR=YES;'", xlsFilePath))
                conn.Open()
                Dim strTableQ(ds.Tables.Count) As String
                Dim i As Integer = 0

                'making table query
                For i = 0 To ds.Tables.Count - 1
                    strTableQ(i) = "CREATE TABLE [" & ds.Tables(i).TableName & "]("

                    Dim j As Integer = 0
                    For j = 0 To ds.Tables(i).Columns.Count - 1
                        Dim dCol As DataColumn
                        dCol = ds.Tables(i).Columns(j)
                        strTableQ(i) &= " [" & dCol.ColumnName & "] varchar(255) , "
                    Next
                    strTableQ(i) = strTableQ(i).Substring(0, strTableQ(i).Length - 2)
                    strTableQ(i) &= ")"

                    Using cmd As New OleDb.OleDbCommand(strTableQ(i), conn)
                        cmd.ExecuteNonQuery()
                    End Using
                Next

                'making insert query
                Dim strInsertQ(ds.Tables.Count - 1) As String
                For i = 0 To ds.Tables.Count - 1
                    strInsertQ(i) = "Insert Into " & ds.Tables(i).TableName & " Values ("
                    For k As Integer = 0 To ds.Tables(i).Columns.Count - 1
                        strInsertQ(i) &= "@" & ds.Tables(i).Columns(k).ColumnName & " , "
                    Next
                    strInsertQ(i) = strInsertQ(i).Substring(0, strInsertQ(i).Length - 2)
                    strInsertQ(i) &= ")"
                Next

                'Now inserting data
                For i = 0 To ds.Tables.Count - 1
                    For j As Integer = 0 To ds.Tables(i).Rows.Count - 1
                        Using cmd As New OleDb.OleDbCommand(strInsertQ(i), conn)
                            For k As Integer = 0 To ds.Tables(i).Columns.Count - 1
                                cmd.Parameters.AddWithValue("@" & ds.Tables(i).Columns(k).ColumnName.ToString(), ds.Tables(i).Rows(j)(k).ToString())
                            Next
                            cmd.ExecuteNonQuery()
                            cmd.Parameters.Clear()
                        End Using
                    Next
                Next
                conn.Close()
                Cursor.Current = Cursors.Default

            End Using
        End If
    End Using
End Sub

Also note that a form that you display with ShowDialog() method must be disposed too.