I Have a scenario where i developed a logic in Apex and was using a Time based workflow Functionality to mark the Checkbox to "True" after 5 mins of Lead Creation DateTime. 

Let me put some light on the 5 min illusion for running the Workflow which is by Default has a functionality to run in 1 hr, I created a formula field which stores value 55 mins past the created date and i scheduled the workflow to run after 1 hr of the formula which logically evaluates to 5 mins after the Lead Created Date.

After careful consideration i decided to Deactivate and Delete the Time dependent Workflow and it's action and include the logic in trigger itself, now the Issue is when i'm creating a New Lead and Try to convert it i'm Getting below Error.

Error: Unable to convert lead that is in use by workflow

I searched all the forums and blogs and everywhere it was stated to check the following.
1. Any pending actions in Setup-> Time-Based Workflow-> Search ----> Done, I found none for that lead record in my sandbox.
2. Check any Pending Approval Actions for that Lead Record   -----> Done, I found none for the Lead Record.

Note :- When i delete and undelete the record(from recycle bin) then it's getting successfully converted.

Not sure what am i missing here, I don't want to do this delete undelete and want a permanent fix to it, Any help here will be appreciated. It's Urgent..!! 

Thanks,
Abhishek.