Heavy flicker/flashing on external monitors using resolutions higher than 1920x1080

Laptop model: Lenovo P51 20HH0011US
OS: Fresh install from USB ‘Ubuntu GNOME 16.04.4 LTS’
Monitors: Dell U2415b at 1920x1200, Asus PB278 at 2560x1440

Expected behavior: We install Ubuntu 16.04.4, plug in additional monitors and those monitors work at the native resolution.

Actual behavior: This one is going to be hard to describe. But when we plug in a monitor, that monitor will flicker/flash extremely fast. With both HDMI and miniDP outputs. Most of the company has two external monitors and when we plug in a second monitor one or both of the external monitors flickered on 14 of the 15 machines that we tested. We also tested with 20 or so monitors through our process of trying to isolate the problem. I will leave links of the video that we took of the issue. From the online preview you cannot tell what the problem is, but if you download the videos and play them with VLC or something locally, you should be able to see what we are talking about.
https://drive.google.com/file/d/1oZQwIf8uaUEytQPQdihIy3eCpVRLe7-T/view?usp=sharing
https://drive.google.com/file/d/1eBrfXouqXhddobGHZijM_G4qNIKiLtaI/view?usp=sharing

We have noticed that if we change the resolution down to 1920x1080 the issue goes away.

The monitors do not flicker on other models of Lenovo’s that we have tried. They also do not flicker with the same computer but running Windows or on any macbook that we have tried. The other weird issue is that once the monitor starts flickering, it stays flickering for about an hour even without a computer plugged into it or if we plug in a different computer that did not make that monitor flicker before it was plugged into a P51 running Ubuntu gnome 16.04.4.
Our current workaround is to install Ubuntu MATE 16.04.4 instead of gnome. The monitors work at native resolutions with MATE.
Let us know if there is anything else we can do to help with this issue.

ProblemType: Bug
DistroRelease: Ubuntu 16.04
Package: xorg 1:7.7+13ubuntu3
ProcVersionSignature: Ubuntu 4.13.0-43.48~16.04.1-generic 4.13.16
Uname: Linux 4.13.0-43-generic x86_64
ApportVersion: 2.20.1-0ubuntu2.15
Architecture: amd64
CompizPlugins: No value set for `/apps/compiz-1/general/screen0/options/active_plugins'
CompositorRunning: None
CurrentDesktop: GNOME
Date: Tue May 29 15:24:31 2018
DistUpgraded: Fresh install
DistroCodename: xenial
DistroVariant: ubuntu
ExtraDebuggingInterest: Yes
GraphicsCard:
 NVIDIA Corporation Device [10de:13b6] (rev a2) (prog-if 00 [VGA controller])
   Subsystem: Lenovo Device [17aa:2251]
InstallationDate: Installed on 2018-05-29 (0 days ago)
InstallationMedia: Ubuntu-GNOME 16.04.4 LTS "Xenial Xerus" - Release amd64 (20180228)
MachineType: LENOVO 20HH0011US
ProcEnviron:
 TERM=xterm-256color
 PATH=(custom, no user)
 XDG_RUNTIME_DIR=<set>
 LANG=en_US.UTF-8
 SHELL=/bin/bash
ProcKernelCmdLine: BOOT_IMAGE=/vmlinuz-4.13.0-43-generic.efi.signed root=/dev/mapper/ubuntu--gnome--vg-root ro quiet splash vt.handoff=7
SourcePackage: xorg
Symptom: display
UpgradeStatus: No upgrade log present (probably fresh install)
dmi.bios.date: 10/20/2017
dmi.bios.vendor: LENOVO
dmi.bios.version: N1UET41W (1.15 )
dmi.board.asset.tag: Not Available
dmi.board.name: 20HH0011US
dmi.board.vendor: LENOVO
dmi.board.version: SDK0J40697 WIN
dmi.chassis.asset.tag: No Asset Information
dmi.chassis.type: 10
dmi.chassis.vendor: LENOVO
dmi.chassis.version: None
dmi.modalias: dmi:bvnLENOVO:bvrN1UET41W(1.15):bd10/20/2017:svnLENOVO:pn20HH0011US:pvrThinkPadP51:rvnLENOVO:rn20HH0011US:rvrSDK0J40697WIN:cvnLENOVO:ct10:cvrNone:
dmi.product.family: ThinkPad P51
dmi.product.name: 20HH0011US
dmi.product.version: ThinkPad P51
dmi.sys.vendor: LENOVO
version.compiz: compiz N/A
version.ia32-libs: ia32-libs N/A
version.libdrm2: libdrm2 2.4.83-1~16.04.1
version.libgl1-mesa-dri: libgl1-mesa-dri 17.2.8-0ubuntu0~16.04.1
version.libgl1-mesa-dri-experimental: libgl1-mesa-dri-experimental N/A
version.libgl1-mesa-glx: libgl1-mesa-glx 17.2.8-0ubuntu0~16.04.1
version.xserver-xorg-core: xserver-xorg-core N/A
version.xserver-xorg-input-evdev: xserver-xorg-input-evdev N/A
version.xserver-xorg-video-ati: xserver-xorg-video-ati N/A
version.xserver-xorg-video-intel: xserver-xorg-video-intel N/A
version.xserver-xorg-video-nouveau: xserver-xorg-video-nouveau N/A