I have managed to resolve this issue by delete all the items from the History List including from the Recycle Bin (it seem that the History List or Workflow somehow maintain a reference to delete columns which was creating this issue).
In one of my test tenants, I had to wait for about 24 hours after deleting items from the history list to get this fixed.