Lo que quieres lograr es relativamente sencillo, para lograrlo basta con sobreescribir la función ModelAdmin.has_delete_permission:
class MiModeloAdmin(admin.ModelAdmin):
def has_delete_permission(self, request, obj=None):
if obj and obj.eliminado:
return False
return True
Esta función indica si se tiene o no permisos para eliminar el objeto, entonces, si está eliminado lógicamente retornamos False
que es exactamente lo que quieres lograr.