More information below - my conclusion is this is a bug in ADO.NET.

I am using a dataset as a data cache in a winforms application.  In one of
the forms of the application, the user can perform actions which result in
the addition or deletion of rows in a table.  The user also has access to
Undo functionality.  If the user deletes a row (thus changing the RowState
to Deleted), and then performs an Undo (which recreates the row) there are
now two rows in the table with the same primary key.  One has a state of
Added, and one has a state of Deleted.   Then the user hits the save button.
In the resulting operation, I perform deletes first, followed by additions
and modifications.  For deletes, I ask for just the deleted rows using
GetChanges() and save all those changes successfully.  Then I ask for all
additions and modifications, and I get deleted rows as well in the case of
the undone deleted row.

My options currently, as I see them are:
1. Every time an undo is performed that results in a new row, remove all
rows with the same primary key that have a state of Deleted.  This results
in a problem though, because if the user performs a redo, the new row will
be deleted and moved to a detached state since it was in an inserted state.
Then, when the user goes to save, the row will not be deleted.

2. When I save additions and modifications, save on a row by row basis, and
skip the ones with Deleted state.
This seems to be my only real alternative.

Any suggestions are very welcome.