I have a solution to this issue that is probably the cleanest I have seen. I will allow you to make the fewest changes to your code and continue using the RowDeleting and RowDeleted events for the GridView.
Currently when you build a command field for a delete button it will look something like this.
<asp:CommandField ButtonType="Image" DeleteImageUrl="images/delete.gif" ShowDeleteButton="true" />
By Changing the ButtonType to "Link" and modifying the DeleteText you will have the same delete image that works exactly like the Image Button Type but without the double firing event. Here is the modified code.
<asp:CommandField ButtonType="Link" DeleteText="<img src='images/delete.gif' alt='Delete this' border='0' />" ShowDeleteButton="true" />
Additionally, I am constantly being asked about how to add a confirm dialog box to the delete button. You can use the following code on the RowDataBound event to add the confirmation.
If e.Row.RowType = DataControlRowType.DataRow Then
Dim lnk As LinkButton = e.Row.Cells(1).Controls(0)
lnk.OnClientClick = "if(!confirm('Are you sure you want to delete this?')) return false;"
End If
I hope this helps!