We have a group policy applied to all of our computers. In this policy, here's what we have configured under "Computer Configuration > Administrative Templates > Windows Components > Windows Update:"

- Do not display 'Install Updates and Shut Down' option in Shut Down dialog box: ENABLED

- Configure Automatic Updates: ENABLED (4 - Auto download and schedule the install, 0-Every day, 03:00)

- Reschedule Automatic Updates scheduled installations: ENABLED (5 minutes)

- No auto-restart with logged on users for scheduled automatic updates installations: ENABLED

- Allow Automatic Updates immediate installation: ENABLED

- Re-prompt for restart with scheduled installations: ENABLED (240 minutes)

- Allow non-administrators to receive update notifications: ENABLED

My understanding is that these settings should allow Automatic Updates to run and install Windows updates, regardless of whether an admin is logged in or not.

However, when I, as an admin, go to someone's computer - someone who's setup as a non-admin - and I log in to their computer, most of the time, Automatic Updates will run and find new updates to install. But, Automatic Update should have run before I got there while the user was logged in.

What are we doing wrong?

Not sure if this will help, but I discovered something suspicious: In Group Policy, when I highlight the policy with the above settings and I click the "Settings" tab in the right pane, it reports all of the policy's settings. Included in the report are all of the settings above, EXCEPT the one for "Allow non-administrators to receive update notifications." Is that normally not reported, or could that be a clue to our problem?

No, that's normally reported. I would suggest perhaps creating a test OU, block inheritance, and place a machine there with a new GPO applied to the OU that sets these again.