Answer is too late, but may be helpful for future visitors.
when I have data on my phone and factory-reset the phone, the data is unrecoverable, since a new key for the encryption is being created and the old one is getting deleted. Am I correct?
You are right.
what happens when I delete data on my phone and then reset the phone - can the deleted data be recovered?
It makes no difference. If luckily the data you deleted is available on the filesystem and data blocks aren't still overwritten, but the problem is it's still encrypted at the lower block level (
userdata) which we can't decrypt after factory reset.
Additionally, during factory reset with stock recovery on newer Android devices, filesystem creation is preceded by
BLKSECDISCARD, which issues
TRIM command to whole block device (
userdata) and should Erase it completely (that's where flash storage differs from traditional HDDs).
Therefore the data is no way recoverable.
For details see: How to make a complete factory reset, without anyone being able to retrieve my data?