Make sure the sidecar (*.sdr/) folder is deleted from the device.
It contains the APNX (as a *.apnx file which then gets merged

into the *azw3{r,f} files, or at least they disappear anyway).
You must purge all traces of the book.
If you deleted the book using calibre's Device view, that *should* happen automatically.