There is a scheduled job that can remove permanent editing. Have you tried to run it?
On a CMS6 site recently I had the same problem, pages in the page tree had the "currently edited by [user]" icon, but when checking the page, permanent editing was actually NOT enabled.
Running the scheduled job Remove Autosaved Page Drafts solved it for me (note the default setting is to remove drafts older than 3 days - can be changed in episerver.config, see the 'draftRetainPeriod' attribute in Paul's blog post)
I have been trying to resolve an issue we are seeing in CMS7 ( I have seen it in the past in CMS6)
We have a page that has been published but it is still saying it is being edited. The person who is apparently editing it has loged out of CMS, there are no pages that are marked "Not Ready" and the user is definatly not editing the page.
However whenever anyone goes into the CMS they are seeing the page marked as being edited. Is there a way to stop this from happening?