New-MailboxSearch Error – Parameter Cannot Be Found

We're running Exchange 2013 and attempting to follow Microsoft's example 3 for an eDiscovery search on Public Folders using the Exchange Management Shell:

New-MailboxSearch -Name "Contoso Litigation" -AllSourceMailboxes $true -AllPublicFolderSources $true -SearchQuery '"price list" AND "contoso"' -StartDate "01/01/2015" -TargetMailbox "Discovery Search Mailbox"
Start-MailboxSearch "Contoso Litigation"

The user executing the commands has been assigned the "Discovery Management" role in Exchange, as required. However, when the first command is executed, it just produces the following error:

A parameter cannot be found that matches parameter name
'AllSourceMailboxes'.

The documentation for the New-MailboxSearch command states that this parameter is valid for both Exchange 2013 and 2016. Additionally, executing Get-Help New-MailboxSearch spits out the following list of parameters:

SYNTAX
New-MailboxSearch -Name <String> [-AllPublicFolderSources
<$true | $false>] [-AllSourceMailboxes <$true | $false>] [-Confirm
<SwitchParameter>] [-Description <String>] [-DomainController <Fqdn>]
[-EndDate <ExDateTime>] [-EstimateOnly <SwitchParameter>]
[-ExcludeDuplicateMessages <$true | $false>] [-Force
<SwitchParameter>] [-IncludeKeywordStatistics <SwitchParameter>]
[-IncludeUnsearchableItems <SwitchParameter>] [-InPlaceHoldEnabled
<$true | $false>] [-InPlaceHoldIdentity <String>] [-ItemHoldPeriod
<Unlimited>] [-Language <CultureInfo>] [-LogLevel <Suppress | Basic |
Full>] [-MessageTypes <KindKeyword[]>] [-PublicFolderSources
<PublicFolderIdParameter[]>] [-Recipients <String[]>] [-SearchQuery
<String>] [-Senders <String[]>] [-SourceMailboxes
<RecipientIdParameter[]>] [-StartDate <ExDateTime>]
[-StatusMailRecipients <RecipientIdParameter[]>] [-TargetMailbox
<MailboxIdParameter>] [-WhatIf <SwitchParameter>] [<CommonParameters>]

The same error also appears for the -AllPublicFolderSources parameter if the -AllSourceMailboxes is removed from the command.

Why are these clearly documented parameters not being accepted? What could be preventing this from working?

Update

So I've been digging into the workings of powershell and learned that the command being executed locally is merely a small powershell function which "proxies" the command and parameters to the Exchange server via "implicit remoting" (the Exchange Management Shell basically connects to the server via New-PSSession and then does an Import-PSSession). The real cmdlet executes on the server and exists in a .NET binary.

Decompiling that binary reveals the following parameters in the NewMailboxSearch class:

private const string ParameterAllPublicFolderSources = "AllPublicFolderSources";
private const string ParameterAllSourceMailboxes = "AllSourceMailboxes";
private const string ParameterDescription = "Description";
private const string ParameterEstimateOnly = "EstimateOnly";
private const string ParameterExcludeDuplicateMessages = "ExcludeDuplicateMessages";
private const string ParameterForce = "Force";
private const string ParameterIncludeKeywordStatistics = "IncludeKeywordStatistics";
private const string ParameterIncludeRemoteAccounts = "IncludeRemoteAccounts";
private const string ParameterIncludeUnsearchableItems = "IncludeUnsearchableItems";
private const string ParameterInPlaceHoldEnabled = "InPlaceHoldEnabled";
private const string ParameterInPlaceHoldIdentity = "InPlaceHoldIdentity";
private const string ParameterItemHoldPeriod = "ItemHoldPeriod";
private const string ParameterLanguage = "Language";
private const string ParameterLogLevel = "LogLevel";
private const string ParameterManagedBy = "ManagedBy";
private const string ParameterMessageTypes = "MessageTypes";
private const string ParameterPublicFolderSources = "PublicFolderSources";
private const string ParameterRecipients = "Recipients";
private const string ParameterSearchQuery = "SearchQuery";
private const string ParameterSenders = "Senders";
private const string ParameterSourceMailboxes = "SourceMailboxes";
private const string ParameterStatusMailRecipients = "StatusMailRecipients";
private const string ParameterTargetMailbox = "TargetMailbox";

So, the cmdlet should accept the parameters which are failing.

However, executing (Get-Command New-MailboxSearch).Definition in the Exchange Management Shell dumps out the code for the local powershell function, and that only lists the following parameters:

param(
  ${Description},
  ${DomainController},
  ${EndDate},
  ${EstimateOnly},
  ${ExcludeDuplicateMessages},
  ${Force},
  ${IncludeKeywordStatistics},
  ${IncludeUnsearchableItems},
  ${InPlaceHoldEnabled},
  ${InPlaceHoldIdentity},
  ${ItemHoldPeriod},
  ${Language},
  ${LogLevel},
  ${MessageTypes},
  ${Name},
  ${Recipients},
  ${SearchQuery},
  ${Senders},
  ${SourceMailboxes},
  ${StartDate},
  ${StatusMailRecipients},
  ${TargetMailbox}
)

Therefore it seems like there's some issue with the remote session and how Import-PSSession interacts with it. Unfortunately I'm not expert enough to figure out why.

I tried adding the missing parameters to the local function but it made no difference, and you also can't just execute the real binary cmdlet on the server because you get this error:

Unable to execute the task. Reason: The task can't identify the user
that is executing the task.

Apparently the cmdlet can only be used through a remote session.

Anyone have any further insight?