The answer through empirical evidence was to force garbage collection: http://technet.microsoft.com/en-us/library/gg492195.aspx
Created a SQL job to run every minute (is faster if ran more often, less to do) to force garbage collection. Once the garbage collector caught up, as it will stop after so much time (even if not fully completed) all went away.
This also released the delete entries from the disk.
Hope this helps someone, even Microsoft Support ticket opened did not figure this one out.