Can't delete user profile of deleted domain account

Thank you , I know that he can't logon as the account does not even exist on Active Directory anymore
Its not only the space that concerns us , its the user profile and its related settings across the system

I know that we could simply delete the folder , if that is all that is required then why is the "user profile" delete option included as per the last image?

Hi Barwa.
The "unknown users" seen in the gui are "mapped" through the registry HKU\<SID> where SID is unique for every local and doman account. Since you do not know the domain SIDs of the deleted accounts you can simply search for some familiar path (ie. under XP C:\Documents and Settings\<domainusername>) - and delete the whole SID-tree.

Settings specific to these users should not affect anyone else on the system. This includes per user registry hives, as it they are stored in each user's folder under "Documents and Settings" (in NTUSER.DAT). Deleting the user's folder from "Documents and Settings" should suffice in most cases. Once their folder is deleted (or at least their NTUSER.DAT file) they will disappear from the list in the "User Profiles" dialog... although this does not remove them from the "HKLM\Software\Microsoft\Windows NT\CurrentVersion\ProfileList" registry key.

If you would like to automate the deletion of user profiles that do not exist on the domain, I've attached a batch file that will accomplish this. WARNING! This script has no way of knowing if these users are former domain members, so it will prompt you to delete ANY local profile folder. System folders such as All Users, Default User, Administrator, etc. will be automatically ignored. If needed, I also have a version of this script that will instead select disabled domain accounts.

This script could be easily modified to not prompt for user input, making it much more efficient than delprof. However, I highly recommend testing it out before doing this. I have the actual delete command commented out, so when you first run it you will only be shown what profiles it will find. Thoroughly test this in your environment (with the delete command disabled) before using it to delete user profile folders.

@echo off
setlocal enabledelayedexpansion
cls
echo.
echo WARNING! This script will prompt you to delete user folders for ANY user
set /p UserInput=  not found on the domain. Are you sure you want to proceed^? ^(Y/N^): 
if /i "%UserInput%" equ "y" goto Start
goto End 
:Start
echo.
echo Searching for local user accounts, please wait... 
for /f "tokens=*" %%i in ('dir /a:d /b "%SYSTEMDRIVE%\Documents and Settings" ^| find /v /i "Administrator" ^| find /v /i "All Users" ^| find /v /i "Default User" ^| find /v /i "LocalService" ^| find /v /i "NetworkService"') do (
	for /f "tokens=1-20" %%I in ('net user %%i /domain 2^>^&1^| find /i "The user name could not be found."') do (
		echo.
		echo The user account "%%i" does not exist in Active Directory.
		set /p UserInput=Would you like to delete this user's local profile? ^(Y/N^): 
		if /i "!UserInput!" equ "y" (
			echo.
			echo Removing user account for user "%%i"...
			echo ^(With profile deletion enabled, the following folder would be deleted:
			echo  "%SYSTEMDRIVE%\Documents and Settings\%%i"^)
			REM Uncomment the following section to enable deleting user profiles:
			REM if "%%i" neq "" rmdir /s/ q "%SYSTEMDRIVE%\Documents and Settings\%%i"
		)
	)
) 
:End
echo.
echo Press any key to exit...
pause>NUL
endlocal
                                              

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:

Since these profiles of the "deleted user accounts" are no longer required , I am following a 2-step approach as follows:

1. Delete the related registry entries as per oBdA comments above 
2. Delete the folder tree of each user under c:\documents and settings 

That's what I said above: there are still handles into the user's profile folder open, which is why the "Delete" option was disabled, and why you can't delete the folder now.
Reboot the machine, try again.

Yes, Windows has a nasty habit of not fully unmounting registry hives at logout (due to open application handles as oBdA suggested). Although this will not help with the computers you are currently trying to cleanup, Microsoft's "User Profile Hive Cleanup Service" will can help you avoid this in the future. Once installed, it monitors and automatically terminates open application handles at logout (in order to properly unmount the user's registry hive).

http://www.microsoft.com/downloads/details.aspx?FamilyId=1B286E6D-8912-4E18-B570-42470E2F3582&displaylang=en

The machine was rebooted several times during the last 30 days

I have already used Process Explorer from Sysinternals to check if any processes are running under any of these accounts but nothing was found

I've seen this happen before. I didn't think the "User Profile Hive Cleanup Service" would help you this time, because I assumed a reboot would fix it. Try installing it (you'll may need to restart again after installation in order for it to work).

If that doesn't work (or if you prefer an alternative), perhaps there is something running at startup from their user profile for some reason. Try this: show hidden files and protected system files, open up that users profile folder, then delete everything you can (most likely everything but "NTUSER.DAT" and "ntuser.dat.LOG"). Now restart, and you should be able to fully delete the user's profile.

While this could be a major hassle to do individually on each computer, deleting all possible files for a specific user fairly simple to do in a batch file:

@echo off
set UserFolder=
set /p UserFolder= Enter the login name of the user you wish to delete:  
:: Check to make sure a user account gets specfied. This is done to ensure
:: that the entire "Documents and Settings" folder does not get deleted.
if "%UserFolder%" equ "" goto :EOF
if "%UserFolder%" equ "." goto :EOF
if "%UserFolder%" equ "\" goto :EOF
if "%UserFolder%" equ "/" goto :EOF 
rmdir /s /q "%SYSTEMDRIVE%\Documents and Settings\%UserFolder%"
echo.
echo Done. 
echo.
echo Press any key to exit...
pause>NUL
set UserFolder=
                                              

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:

Did you ever try to load this user's hive into regedit, and then forgot to unload it again?
Is the Delete button available when you're logged on using another administrative account?

I remember also cases where the NTUSER.DAT was as if opened and even sysinternals could not find any  handles adressing the file.
BUT what I remember was beong used long time ago to change some open handle files was renaming them. Something like REN NTUSER.DAT NTUSER.BAK?
If it works at this point the handle is still open to the renamed file but after restart it should definitely not "catch" the new name anymore

Partially