Hi, for those with the same error, I found how to avoid the Shape or Row not found by using AutoCreate method of IAnnoClassAdmin3 class. I set it to false, add polygons then set it back to true. This way, I don't need to delete the feature linked annotation because it is not created...
' Disable annotation AutoCreate
Dim pACAdmin As IAnnoClassAdmin3
pACAdmin = CType(MyFeatureClass.Extension, IAnnoClassAdmin3)
pACAdmin.AutoCreate = False
[...] : Code that create polygon
pACAdmin.AutoCreate = True