So after reworking the batch files a tad, I have a work around, but it doesn't make a lot of sense as to why the issue is there to begin with, but what I did was break up the batch as below:
CC-1.bat:
psexec @COMP.txt -c -d -f -s \\server\INSTALLS\CCleaner\ccsetup.exe /S
psexec @COMP.txt -c -d -f -s CC-2.bat pause
CC-2.bat:
DEL "%SystemDrive%\Users\Public\Desktop\CCleaner.lnk" DEL "C:\Documents and Settings\All Users\Desktop\CCleaner.lnk" /F /Q RMDIR /S /Q "%SystemDrive%\ProgramData\Microsoft\Windows\Start Menu\Programs\CCleaner" RMDIR /S /Q "C:\Documents and Settings\All Users\Start Menu\Programs\CCleaner" COPY /y "\\server\INSTALLS\CC\ccleaner.ini" "C:\Program Files\CCleaner"