Sharepoint - Dealing with List View Threshhold

I know that you've mentioned that your solution should not involve increasing the list view threshold, however you can do this on a list-by-list basis if required (assuming your SharePoint in on-premises) using PowerShell.

The PowerShell to do this is:

$web = Get-SPWeb http://WebURL.domain.com
$list = $web.Lists["ListName"]
$list.EnableThrottling = $false
$list.Update()

Note that the "ListName" is the name of the list as it appears within the UI, not the URL.

To determine whether the list has throttling enabled and whether is actually throttled, use:

$list.EnableThrottling
$list.IsThrottled

And to return the list to the default throttling set within Central Administration, use:

$list.EnableThrottling = $true
$list.Update()

The first filter of a View must return less than the set List View Threshold, otherwise it will trip the LVT exceeded message.

If this is an on-premise solution you can increase the list view threshold by going to:

Central Admin -> Manage Web Applications -> select the web application you want to modify -> general settings -> select resource throttling (drop down). In the form you have a field called List View Threshold, here you can increase the threshold limit.

Increasing the limit will affect the performance, and it is not recommended to do so, get to know the consequences of increasing the limit. I have done this once (limit to 10 000) with some lower performance, so it worked fine in my case.

If this is a lookup issue you can overcome this problem with queries where the returned result is lower than 5000. For example if you have a custom form where you use select2 on a field, and the options is set by the returned result from the query.