Upon further investigation into the profiles that wouldn't be deleted, they all had the following folder remaining C:\Users\username\AppData\Local\Temp\3\acrord32_sbx which contained Z@...tmp files.
These files are created when a user prints a PDF document (something to do with how it deals with fonts...). They should delete on log off, but are now locked and the system cannot delete them as part of the log off process.
The forums are full of posts about this. Adobe have never resolved this (at the time of typing).
Many people have resolved this issue (including me) by uninstalling a Windows Security Update. The problem is, no-one knows exactly which one as updates are often superseded by others as they become released.
Various KB's to uninstall have been suggested in forums (such as https://forums.adobe.com/thread/1558909) with mixed success, however the update that we removed that has not been suggested elsewhere was KB3034344
If you can't find this update installed on the affected RDS Server, have a look for the following
KB3034344 update was replaced by/replaces
It's up to you whether you uninstall security updates. You need to review the notes of the update and decide if it going to present any risks.
Confirmation of Steps
1) Identify the Security Update KB (ideally in a lab environment)
2) Uninstall the update off the RDS Server (using add/remove programs / show installed updates)
3)Reboot the server
4) Manually delete all old roaming profiles that exist on the RDS Servers c:\users (except Public, Default and Administrator)
5) Reboot the server again
6) Test. Log on as a domain user, print a PDF. Log off and check the roaming profile is deleted off the RDS Server.
7) Using WSUS, SCE or any other patch management software, Decline this update so it is not reinstalled in the future.
*** Update ***
The issue appeared again - Microsoft must have released another update which causes the issue again. I cross checked the date it started to occur and Windows Updates and there were over 20 updates. I wasn't able to identify the update but instead created an acroct.ini file which resolves the issue.
1. Open Notepad
2. Paste the following
3. Save as 'acroct.ini'
4. Place the file in c:\windows
Tip: If you have multiple machines that need this fix, place the ini file on a share and use group policy preferences to copy the file out to the machines c:\windows folder.