The test doesn't seem to be flaky:
https://test-results.appspot.com/dashboards/flakiness_dashboard.html#testType=unit_tests&tests=ChromeBrowsingDataRemoverDelegateTest.RemoveProtocolHandler

Is the test consistently failing for you? Does this need a specific build configuration?

This test fails consistently for me with following arguments:
is_debug = true
is_component_build = true
target_cpu = "x64"
enable_nacl = false
use_jumbo_build = true

It also fails in non-debug/non-component mode for me.

The logs show an error message:
[11048:13700:0605/145722.968:108287813:ERROR:shell_integration_win.cc(569)] Chrome could not be set as default handler for test1.
[11048:13700:0605/145722.969:108287813:ERROR:shell_integration_win.cc(569)] Chrome could not be set as default handler for test2.

So Chrome (probably unit_test.exe) tries to register as default handler with the OS. I wonder why this happens on your machine but not on our Win7 trybots. 

Could you try if SiteSettingsCounterTest.ProtocolHandlerCounting runs successfully for you? 
Could you also try ProtocolHandlerRegistryTest.TestOnAcceptRegisterProtocolHandler?

Yes, both tests pass for me but "Chrome could not be set as default handler for test1/test2" message is still displayed.

That probably means that the handler for "test2" gets deleted although it shouldn't because it was created at now()-1day and we only delete handlers between now()-1hour and max().

The test also fails on two other machines with Windows 8.1 Update 1 installed. Two builds were tested: 32- and 64-bit. Test failed in both cases.

We ran the test on Win10 x64 with is_debug enabled and disabled and also with your exact config and the test always succeeds. 

You could take a look at ProtocolHandlerRegistry::ClearUserDefinedHandlers, that's where the deletion is happening. I guess if there is some issue, it will be somewhere in the deletion code.

OK. Thanks for the hint. I'll try to take a look when I find some spare time.

The root cause is that ProtocolHandlerRegistry::OnSetAsDefaultProtocolClientFinished() is called with NOT_DEFAULT |state|. This causes ClearDefault(protocol) to be called. This happens anytime we try to set default protocol handler from test.

It works in two cases however:
1. If unit_tests.exe is run with elevated privileges.
2. If setup.exe exists and User Account Control (UAC) is disabled.
  a) ShellUtil::RegisterChromeForProtocol() calls ElevateAndRegisterChrome() in this case which runs setup.exe as admin.
  b) setup.exe isn't build with unit_tests.exe by default because there's no dependency path between //chrome/test:unit_tests and //chrome/installer/setup:setup.

There's also related issue. The test doesn't cleanup changes it does in Windows registry. All entries written under HKEY_LOCAL_MACHINE stay there when the test finishes. ShellUtil::RegisterChromeForProtocol() returns |true| immediately if Chrome is already registered for protocol. It means that if entries has been written once from elevated process, then subsequent test runs (without elevated privileges) will pass.

I've tried to force the test to use a temporary path under HKEY_CURRENT_USER. We don't need elevated privileges to write there and we can delete all entries inside the temporary path during the test tear down. I did following:
1. Use registry_util::RegistryOverrideManager from base/test to map HKEY_LOCAL_MACHINE to temporary path. (a side note: RegistryTestData can be easily reimplemented to use RegistryOverrideManager what makes it simpler as RegistryOverrideManager does all the cleanup itself).
2. Add ShellUtil::OverrideRegistrationRootForTesting() method to force DetermineRegistrationRoot() to return HKEY_CURRENT_USER in tests.

Unfortunately it's not enough.
ProtocolHandlerRegistry::OnSetAsDefaultProtocolClientFinished() is called with the |state| argument calculated in DefaultProtocolClientWorker::CheckIsDefaultImpl(). It internally uses ProbeCurrentDefaultHandlers() and IApplicationAssociationRegistration interface so it's not easy to mock it.

All ShellUtil functions are static what makes creating mocks difficult. I don't want to make a serious changes to this code without prior notification. Do you have any suggestions how to fix this issue properly?

Hm, maybe the bots run without UAC and build all targets anyway, so the test succeeds for us.
The test checks at the end that no protocol handlers exists. I expected that this is sufficient cleanup.

We could use the same approach as ProtocolHandlerRegistryTest and use a fake delegate. This way, the windows registry would not be used at all and we get proper cleanup after the test:
https://cs.chromium.org/chromium/src/chrome/browser/custom_handlers/protocol_handler_registry_unittest.cc?l=135&rcl=abf32b0dc47958ca04e0cddc0cef155da002248d

I found another possible workaround in RegisterProtocolHandlerBrowserTest:
https://cs.chromium.org/chromium/src/chrome/browser/custom_handlers/protocol_handler_registry_browsertest.cc?l=61&rcl=abf32b0dc47958ca04e0cddc0cef155da002248d

Thanks for investigating!

Thanks for help in finding the solution! I've uploaded a review at https://chromium-review.googlesource.com/c/chromium/src/+/1348115

The following revision refers to this bug:
  https://chromium.googlesource.com/chromium/src.git/+/47ddfcfb6e439e6a1f0a8487cd4e870ae573ab12

commit 47ddfcfb6e439e6a1f0a8487cd4e870ae573ab12
Author: Tomasz Moniuszko <tmoniuszko@opera.com>
Date: Thu Dec 13 14:18:42 2018

Avoid modifying Windows registry in RemoveProtocolHandler test

Writing to Windows registry requires elevated privileges and the test
fails on Windows 7 unless it's run as administrator (but in this case
all modifications stay in registry because the test doesn't do the
cleanup during its tear down).

Bug:  849660 
Change-Id: I6cb8e9b2ba30e5bd9af2d8ede97c9bd62ccbc9ca
Reviewed-on: https://chromium-review.googlesource.com/c/1348115
Commit-Queue: Tomasz Moniuszko <tmoniuszko@opera.com>
Reviewed-by: Christian Dullweber <dullweber@chromium.org>
Cr-Commit-Position: refs/heads/master@{#616303}
[modify] https://crrev.com/47ddfcfb6e439e6a1f0a8487cd4e870ae573ab12/chrome/browser/browsing_data/chrome_browsing_data_remover_delegate_unittest.cc