The issue was happening on the iPad but Agenda was also running on my iMac at the same time.
I noticed that when I went to the iMac and deleted the notes there then they finally disappeared on the iPad as well and never returned.
This makes me wonder if although I was deleting the event on the iPad my iMac (Agenda or iCal) was recreating it every time.
I see a similar behavior with notes I created and delete right after creation. It looks like when creating the note sync kicks off and you have to wait some seconds before deleting it again.
This is not related if the note is linked to a cal. event (at least I did not recognize so far)