I’m wondering if something is stuck in the database then that relates to when you had the plugin active there. Still, may want to contact the developer of that plugin to see if they think that could be it. Did you try the site using the default setting of permalinks to see if it self-corrects?
