By default the New-ComplianceSearch cmdlet is part of the Mailbox Search role, which is NOT assigned to the Organization Management Role group. So make sure your user is assigned to a role which does contain the cmdlet definition. You can use the following:
Get-ManagementRole -Cmdlet New-ComplianceSearch
Then for each role returned, check the assignments via Get-ManagementRoleAssignment.