el_koraco, did you read what the shrink dialog says:
You cannot shrink a volume beyond the point where any unmovable files are located. See the "defrag" event in the Application log for detailed information about the operation when it has completed.
Did you check this log?
Also, from the Help:
Additional considerations
When you shrink a partition, certain files (for example, the paging file or the shadow copy storage area) cannot be automatically relocated and you cannot decrease the allocated space beyond the point where the unmovable files are located. If the shrink operation fails, check the Application Log for Event 259, which will identify the unmovable file. If you know the cluster or clusters associated with the file that is preventing the shrink operation, you can also use the fsutil command at a command prompt (type fsutil volume querycluster /? for usage). When you provide the querycluster parameter, the command output will identify the unmovable file that is preventing the shrink operation from succeeding.
In some cases, you can relocate the file temporarily. For example, if the unmovable file is the paging file, you can use Control Panel to move it to another disk, shrink the volume, and then move the page file back to the disk.
If the number of bad clusters detected by dynamic bad-cluster remapping is too high, you cannot shrink the partition. If this occurs, you should consider moving the data and replacing the disk.
Do not use a block-level copy to transfer the data. This will also copy the bad sector table and the new disk will treat the same sectors as bad even though they are normal.
Also read the last reply on the bottom of this page: http://technet.microsoft.com/en-us/libr
31894.aspx
Good luck!
On the topic of OEM installs, a while ago I encountered a Windows laptop (Compaq I think) that had the option to do a clean, Windows-only install from the restore partition. This got rid of all the OEM junk pretty easily. I was happily surprised!