Yes, deleted Slack messages are really deleted. Slack messages are actually deleted as soon as they're marked for deletion.