I had a very similar issue as you had. What actually worked is this:
iTotalColumns = xlWorkSheet.UsedRange.Columns.Count;
iTotalRows = xlWorkSheet.UsedRange.Rows.Count;
//These two lines do the magic.
xlWorkSheet.Columns.ClearFormats();
xlWorkSheet.Rows.ClearFormats();
iTotalColumns = xlWorkSheet.UsedRange.Columns.Count;
iTotalRows = xlWorkSheet.UsedRange.Rows.Count;
IMHO what happens is that when you delete data from Excel, it keeps on thinking that there is data in those cells, though they are blank. When I cleared the formats, it removes the blank cells and hence returns actual counts.