The reason is because I have route 53 records for which I have changed the pulumi name. As such, it creates the new resource but then deletes the old record, but because it does the create first and then the delete, the actual record is actually removed but pulumi thinks it still exists (because the actual record name (e.g. www.domain.com is specific and defined)

The safer option might be refactoring using aliases. Check out this blog post

Cool thanks @freezing-van-87649!