jlawson, this is why I don't think the java update option to install when not logged in will realistically work for us either. We train our users to shut down when they leave and computers here are rarely logged off but powered on.
Instead of as soon as possible, I'd try a schedule that runs every 5 minutes or so.
When I updated Java the last time, I didn't use patch, I used managed software delivery and created a filter that said 'doesn't have X version of java' and pushed that version of java to that filter and had it running every 20 mins. This way if it failed or didn't run because the browser was opened, it would just keep trying every 20 mins. The last part of the MSD was update client config, so once Java was installed, it would fall out of the filter. We still got 10-15% of users calling into the helpdesk who needed java before the install happened and we had to force close the browser and force the update to happen in the agent.
I'm like to get away from this and use patch for Java but seems like it just isn't able to handle the fail case when it fails when browser is opened. Or maybe you can use patch but you need to scope it to a filter instead of all computers, all computers that haven't gotten java yet so it will keep trying?