I am experiencing exactly the same problem. We are using Openfire 3.6.4 with Active Directory, MySQL and Spark 2.5.8.
I created a test user in AD, added to a contact list, logged in as the user and accepted my user request all works fine. I then deleted the user from AD, cleared all caches on the Openfire server and restarted Openfire.
On the PC I de-installed the Spark client and ensured that the spark directory in program files and my Documents and Settings directory had been deleted. I re-installed Spark, logged back in and the deleted user still shows in Offline contacts.
I am unable to search for the user (as expected)
I am unable to move the user from the Offline group into a new group.
If I view the profile of the user I just see the JID
If I look at the MySQL database there is an entry for the user and for me in the ofRoster table there is also an entry for the user in ofPresence.
Is there any way of rectifying this situation as it may stop me deploying Openfire/Spark into our environment?