(Posting the answer to my own question incase anyone else comes to here from a search.)
In order to finally get past this problem I had to do two things:
First, verify that your "Turn on Protected Mode" settings are exactly the same for both "Computer Configuration" and "User Configuration". I don't think it actually matters whether the setting is Enabled/Disabled, or whether Protected Mode is Enabled/Disabled, so long as all of them (11 under Computer Configuration and 11 under User Configuration) are identical.
The quickest way to do this is to use the Group Policy Editor to verify that all of the appropriate settings are configured.
To do this, open the Local Group Policy Editor (start / run / gpedit.msc) and navigate to the “Local Computer PolicyComputer ConfigurationAdministrative TemplatesAll Settings” node. Sort by Setting (if not already done) and scroll down until you see a bunch of "Turn on Protected Mode" settings.
Configure each of these to be the same value. In my case I had originally set these all to be Enabled and Protected Mode Disabled, but once I finally found the registry change (see below), I went back in and set everything to "Not Configured" like it was originally and my solution still worked. The main point is to make them all exactly the same.
Then repeat this process for the “Local Computer PolicyUser ConfigurationAdministrative TemplatesAll Settings” node.
Once this is done, all of your Protected Mode settings should be the same. NOTE: If you use one user to execute your tests and another for system management, go through the process on both users just incase. (I had issues in my setup so I'm not sure if this is required, but it couldn't hurt.)
Second, adjust your registry settings.
Navigate to "HKLMSoftwareMicrosoftWindowsCurrentVersionInternet Settingsones". For every sub-key (0,1,2,3,4), locate the DWORD named "2500". If it doesn't exist, create it. Again, set the value to be identical for all 5 Zones. I used '0', which is Enabled. I believe '3' is Disabled.
Repeat this process for "HKCUSoftwareMicrosoftWindowsCurrentVersionInternet Settingsones" for the user that is using IEDriverServer.exe.
Once you've updated the registry, reboot your machine.
Following these two steps resolved the problem for me after many hours of trying to adjust the settings manually or via the GPO. Other people seem to have had success with either method, but using the registry edits was the only thing that worked in my environment (replicated (and fixed) on two different Jenkins slaves).
NOTE: I'm doing the IEDriverServer manipulation with a named user account for Jenkins. If you're executing your tests as the "Local System" user, you may want to take a look at this answer for further instructions/trouble-shooting.