Resolver is searching in unrelated packages for solution

Description

redirects: on
source https://nuget.org/api/v2

//Build
nuget FAKE == 4.63.0
nuget FSharp.Compiler.Service >= 13.0.0
nuget FSharp.Compiler.Tools >= 4.1.21
nuget FSharp.Formatting
nuget FSharpVSPowerTools.Core
nuget Yaaf.AdvancedBuilding == 0.14.1
nuget NUnit.Runners ~> 2
nuget Mono.Posix

// Project
nuget FSharp.Core >= 4.2.2
nuget SimpleInjector
nuget FSharp.Configuration >= 1.2.0
nuget Yaaf.ApplicationInsights
nuget Microsoft.Owin.Host.HttpListener
nuget Microsoft.Owin.Hosting
nuget Mono.Security
nuget Nancy
nuget Nancy.Owin
// Latest has NullReferenceException...
nuget Nancy.Authentication.Forms
nuget Nancy.Validation.DataAnnotations
nuget Nancy.Viewengines.Razor
nuget Novell.Directory.Ldap
nuget FSharp.Interop.Dynamic
nuget Dynamitey
nuget Lucene.Net
nuget Lucene.Net.Contrib
nuget Lucene.Net.Linq
nuget Yaaf.FSharp.Helper
// Not needed in the future.
nuget Yaaf.Database.MySQL
nuget Yaaf.MessageArchiveManager.MySQL


// Test
nuget NUnit
nuget Foq content: none >= 1.7.2
nuget FsUnit
nuget Unquote

github matthid/Yaaf.FSharp.Helper src/test/Test.Yaaf.FSharp.Helper/MyTestClass.fs
github matthid/Yaaf.Xmpp.Runtime:develop src/test/Test.Yaaf.Xmpp.Runtime/TestHelper.fs

prints

$ .paket/paket.exe update
Paket version 5.84.0
Resolving packages for group Main:
 - FAKE 4.63.0
 - Yaaf.AdvancedBuilding 0.14.1
 - NUnit.Runners 2.6.4
 - FSharp.Compiler.Service 13.0.0
 - FSharp.Core 4.2.2
 - FSharp.Compiler.Tools 4.1.23
 - FSharp.Configuration 1.3.0
 - Dynamitey 1.0.2
 - Foq 1.7.2
 - FSharp.Formatting 2.14.4
 - Foq 1.7.1
 - Foq 1.7.0
 - Foq 1.6.0
 - Foq 1.5.1
 - Foq 1.5.0
 - Foq 1.4.0
 - Foq 1.3.0
 - Foq 1.2.0
 - Foq 1.1.0
 - Foq 1.0.0
 - Foq 0.9.0
 - Foq 0.8.0
 - Foq 0.7.0
 - Foq 0.6.0
 - Foq 0.5.0
 - Foq 0.4.0
 - Foq 0.3.0
 - Foq 0.2.0
 - Foq 0.1.0
 - Dynamitey 0.8.0.6
 - FSharp.Configuration 1.2.0
 - FSharp.Compiler.Tools 4.1.21
 - NUnit.Runners 2.6.3
 - NUnit.Runners 2.6.2
 - NUnit.Runners 2.6.1
 - NUnit.Runners 2.6.0.12051
Performance:
 - Resolver: 5 seconds (1 runs)
    - Runtime: 973 milliseconds
    - Blocked (retrieving package details): 4 seconds (35 times)
    - Not Blocked (retrieving package versions): 886 times
    - Not Blocked (retrieving package details): 1 times
 - Average Request Time: 505 milliseconds
 - Number of Requests: 66
 - Runtime: 8 seconds
Paket failed with
-> There was a version conflict during package resolution.
     Resolved packages:
      - Dynamitey 0.8.0.6
      - FAKE 4.63.0
      - Foq 0.1.0
      - FSharp.Compiler.Service 13.0.0
      - FSharp.Compiler.Tools 4.1.21
      - FSharp.Configuration 1.2.0
      - FSharp.Core 4.2.2
      - NUnit.Runners 2.6.0.12051
      - Yaaf.AdvancedBuilding 0.14.1
     Conflict detected:
      - FSharp.Formatting 2.14.4 requested package FSharp.Compiler.Service: 2.0.0.6
      - Dependencies file requested package FSharp.Compiler.Service: >= 13.0

     Please try to relax some conditions or resolve the conflict manually (see http://fsprojects.github.io/Paket/nuget-dependencies.html#Use-exactly-this-version-constraint).

Result seems to be correct, but something in the resolver is strange:
Why hunt down all versions of Foq? It has absolutely nothing to do with the conflict. Most Foq Versions don't even have dependencies. There is also no way how there could be a version of Foq which would resolve the conflict?

Expected behavior

Stop earlier or try to replace relevant packages

Actual behavior

paket tries to resolve the conflict by searching though "Foq"

Start by reproducing the issue with the shown dependencies and .paket/paket.exe update, then trace the resolver's package-search decisions and conflict handling. The fix is done when unrelated Foq versions are not searched during this conflict, while the relevant FSharp.Compiler.Service conflict is still reported correctly.