Using the Community Edition, any restart will be a cold restart one and potentially resurrect deleted data.
The other thing I can think of is a generation wrap around while a node was down to be upgraded, causing the older (but with higher generation) record to take over when the node comes back (refer to conflict-resolution-policy).
There may be other edge situations but would be a bit less common. Enterprise Licensee can provide logs to Aerospike Support for in depth analysis.