If you create a record, then delete it without saving between the two, it creates a DataRow in the DataTable with the RowState of Deleted even though it has never existed in the database. It was only created in your local DataTable.
When you try to update that DataRow, the TableAdapter will complain that the row's deletion could not be completed because it does not exist in the database. It will think the row was actually deleted by someone else while it was not looking when it actually never existed.
I do not know if it is the source of your problem, but saving after every action would make the problem disappear (although you lose the benefits of a disconnected architecture) so I think it might be it.
There are other ways to go around the problem, none really perfect, but you can put a condition to your deletion code to do table.Rows.Remove(myRow) instead of myRow.Delete() when its RowState is Added.
The human mind's capability to comprehend abstract concepts is limited to the vocabulary it can use to describe it. The more precise the building blocks, the more complex the thoughts that can emerge... Sounds like the evolution of programming languages doesn't it?