Although this article apparently only applied to Windows Vista, the suggestions appear to be quite valid for Windows Server 2008 Terminal Services servers- and are especially useful when profiles are simply deleted rather than being removed using the profile management tools available (and a great read on the subject is here: http://blogs.msdn.com/b/rds/archive/2009/06/02/user-profiles-on-windows-server-2008-r2-remote-desktop-services.aspx)

Removing Profile: http://support.microsoft.com/?kbid=947242