How to determine if a DynamoDB item was indeed deleted?

Try using conditional expressions like

attribute_exists(my_key)

If element doesn't exist conditional check error will be raised

DeleteItemResult#getAttributes() is the way to determine if a DeleteItem operation has actually deleted an item, or not.

If you specify ReturnValue.ALL_OLD and the item was deleted, a map of item attributes is returned, otherwise and empty map is returned. This is the only way to know for sure if the operation was successful. No other confirmation is returned by the API.

Keep in mind that a DeleteItem operation will consume a minimum of 1 write capacity unit every time. If the deleted item is larger than 1KB, consumed capacity will be more than 1.

For reference: http://docs.aws.amazon.com/amazondynamodb/latest/developerguide/CapacityUnitCalculations.html#ItemSizeCalculations.Writes