I have experienced the same issue previously with a few packages, yet running the same thing works fine. But I don't reboot my machines beforehand as we have a lot of staff that work remotely via VPN (construction company). I sometimes wish for a nice office with desktops that I could just WOL at night and push everything out.
Are you seeing this with a lot of packages or just your Java package?
Below is what I am using for our Java deployments. I am calling an uninstall first, then when installing the new version I am also issuing REMOVEOUTOFDATEJRES=1
<?xml version="1.0" encoding="utf-8"?>
<Package>
<Name>APP.Java</Name>
<Description></Description>
<ShutdownOption>0</ShutdownOption>
<ShutdownTime>0</ShutdownTime>
<MaxDuration>900</MaxDuration>
<Rescan>True</Rescan>
<RunMode>2</RunMode>
<Steps>
<Step>
<Nr>1</Nr>
<Name>Uninstall Previous Versions Of Java</Name>
<Type>2</Type>
<ReturnCodes>0,1641,3010</ReturnCodes>
<Success>2</Success>
<Failure>2</Failure>
<Path></Path>
<Parameters></Parameters>
<MSIParameters></MSIParameters>
<MSIName></MSIName>
<MSIVersion></MSIVersion>
<Command>wmic product where "name like 'Java%%'" call uninstall /nointeractive</Command>
<EditMode>False</EditMode>
<Conditions />
</Step>
<Step>
<Nr>2</Nr>
<Name>Check Architecture</Name>
<Type>5</Type>
<ReturnCodes></ReturnCodes>
<Success>3</Success>
<Failure>4</Failure>
<Path></Path>
<Parameters></Parameters>
<MSIParameters></MSIParameters>
<MSIName></MSIName>
<MSIVersion></MSIVersion>
<Command></Command>
<EditMode>False</EditMode>
<Conditions>
<Condition>
<Type>3</Type>
<SpecOne></SpecOne>
<SpecTwo></SpecTwo>
<Operator>5</Operator>
<Value></Value>
</Condition>
</Conditions>
</Step>
<Step>
<Nr>3</Nr>
<Name>Install 32bit</Name>
<Type>1</Type>
<ReturnCodes>0,1641,3010</ReturnCodes>
<Success>5</Success>
<Failure>-3</Failure>
<Path>{PackageShare}\Java\jre-8u191-windows-i586.exe</Path>
<Parameters>/s REMOVEOUTOFDATEJRES=1</Parameters>
<MSIParameters>/i /qn /norestart</MSIParameters>
<MSIName></MSIName>
<MSIVersion></MSIVersion>
<Command>"{PackageShare}\Java\jre-8u191-windows-i586.exe" /s REMOVEOUTOFDATEJRES=1</Command>
<EditMode>False</EditMode>
<Conditions />
</Step>
<Step>
<Nr>4</Nr>
<Name>Install 64bit</Name>
<Type>1</Type>
<ReturnCodes>0,1641,3010</ReturnCodes>
<Success>5</Success>
<Failure>-3</Failure>
<Path>{PackageShare}\Java\jre-8u191-windows-x64.exe</Path>
<Parameters>/s REMOVEOUTOFDATEJRES=1</Parameters>
<MSIParameters>/i /qn /norestart</MSIParameters>
<MSIName></MSIName>
<MSIVersion></MSIVersion>
<Command>"{PackageShare}\Java\jre-8u191-windows-x64.exe" /s REMOVEOUTOFDATEJRES=1</Command>
<EditMode>False</EditMode>
<Conditions />
</Step>
<Step>
<Nr>5</Nr>
<Name>Disable Update Schedule</Name>
<Type>2</Type>
<ReturnCodes>0,1641,3010</ReturnCodes>
<Success>-1</Success>
<Failure>-3</Failure>
<Path></Path>
<Parameters></Parameters>
<MSIParameters></MSIParameters>
<MSIName></MSIName>
<MSIVersion></MSIVersion>
<Command>reg delete "HKLM\SOFTWARE\Wow6432Node\JavaSoft\Java Update\Policy\jucheck" /v "UpdateSchedule" /f</Command>
<EditMode>False</EditMode>
<Conditions />
</Step>
<Step>
<Nr>6</Nr>
<Name>Disable Update Check Time</Name>
<Type>2</Type>
<ReturnCodes>0,1641,3010</ReturnCodes>
<Success>-1</Success>
<Failure>-3</Failure>
<Path></Path>
<Parameters></Parameters>
<MSIParameters></MSIParameters>
<MSIName></MSIName>
<MSIVersion></MSIVersion>
<Command>reg delete "HKLM\SOFTWARE\Wow6432Node\JavaSoft\Java Update\Policy\jucheck" /v "UpdateMin" /f</Command>
<EditMode>False</EditMode>
<Conditions />
</Step>
<Step>
<Nr>7</Nr>
<Name>Disable Update Check</Name>
<Type>2</Type>
<ReturnCodes>0,1641,3010</ReturnCodes>
<Success>-1</Success>
<Failure>-3</Failure>
<Path></Path>
<Parameters></Parameters>
<MSIParameters></MSIParameters>
<MSIName></MSIName>
<MSIVersion></MSIVersion>
<Command>reg add "HKLM\SOFTWARE\Wow6432Node\JavaSoft\Java Update\Policy" /v EnableJavaUpdate /t REG_DWORD /d 00000000 /f</Command>
<EditMode>False</EditMode>
<Conditions />
</Step>
<Step>
<Nr>8</Nr>
<Name>Disable AutoUpdate Check</Name>
<Type>2</Type>
<ReturnCodes>0,1641,3010</ReturnCodes>
<Success>-2</Success>
<Failure>-3</Failure>
<Path></Path>
<Parameters></Parameters>
<MSIParameters></MSIParameters>
<MSIName></MSIName>
<MSIVersion></MSIVersion>
<Command>reg add "HKLM\SOFTWARE\Wow6432Node\JavaSoft\Java Update\Policy" /v EnableAutoUpdateCheck /t REG_DWORD /d 00000000 /f</Command>
<EditMode>False</EditMode>
<Conditions />
</Step>
</Steps>
<SoftwareVersion>7.0.110.2</SoftwareVersion>
</Package>