I've tested all of the responses. And these are the results

 Sancarn1: 10718.9899
 Sancarn2: 1056.0504
 VBasic2008: 8347.2902
 Sancarn3: 720.3811
 IAmNerd2000_2: 1182.7751
 VBasic2008_refac: 2092.3596
 
 IAmNerd2000_1: 5263.4871 - Disqualified due to incorrect address with formatting outside of value range.

I had to modify the code I originally posted as it didn't work in some conditions. The test cases are provided below:

https://pastebin.com/iSmLZXqN

The fastest method turned out to be `Sancarn3` which came from being inspired by code posted by IAmNerd2000.

In this post I'd like to cover the 2 best solutions discussed.

----

# The simple solution

The simplest solution appears to be VBasic2008's version. This is solution is short and easy to understand. If code readability is more important to you than speed use this! **Edit: I've refactored this code slightly which not only makes it faster but also makes it easier to understand**:

 Function RealUsedRange_VBasic2008_refac(sht As Worksheet) As Range
 Dim firstCell, lastCell As Range
 With sht
 'Start at first cell in sheet, go forward and find next cell (i.e. first cell of RealUsedRange)
 Set firstCell = .Cells.Find("*", .Cells(1, 1), Excel.XlFindLookIn.xlValues, , XlSearchOrder.xlByRows)
 If Not firstCell Is Nothing Then
 'Start at last cell in sheet, go back and find previous cell (i.e. last cell of RealUsedRange)
 Set lastCell = .Cells.Find("*", .Cells(1048576, 16384), Excel.XlFindLookIn.xlValues, , XlSearchOrder.xlByColumns, xlPrevious)
 
 'Find combined range between first and last cell
 Set RealUsedRange_VBasic2008_refac = Range(firstCell, lastCell)
 End If
 End With
 End Function

# The optimal solution

If you are more concerned with performance than clean code use this. It restricts the number of calls to slow COM objects property accessors. This is the main reason why this solution is faster than the above simple method:

 Function RealUsedRange_Sancarn3(sht As Worksheet) As Range
 'Get used range
 Dim ur As Range
 Set ur = sht.UsedRange
 
 'If used range is 1x1 then result is 1x1
 If ur.Rows.Count = 1 And ur.Columns.Count = 1 Then
 Set RealUsedRange_Sancarn3 = ur
 Exit Function
 End If
 
 'Find via array
 'Get array of all values (if there is an error, this may be an out of memory error. In this case use find()):
 On Error GoTo URValueError
 Dim v As Variant
 v = ur.Value
 On Error GoTo 0
 
 'Offsets if they exist
 Dim offR, offC As Long
 With ur
 offR = .row - 1
 offC = .Column - 1
 End With
 
 'Define required values
 Dim colMin, colMax, rowMin, rowMax, row, col As Long
 
 'Find min row:
 Dim ubndR, ubndC, lbndR, lbndC As Long
 lbndR = LBound(v, 1)
 lbndC = LBound(v, 2)
 ubndR = UBound(v, 1)
 ubndC = UBound(v, 2)
 
 For row = lbndR To ubndR
 For col = lbndC To ubndC
 If Not IsEmpty(v(row, col)) Then
 rowMin = row
 GoTo NextNum
 End If
 Next
 Next
 NextNum:
 'Find max row
 For row = ubndR To lbndR Step -1
 For col = lbndC To ubndC
 If Not IsEmpty(v(row, col)) Then
 rowMax = row
 GoTo NextNum2
 End If
 Next
 Next
 NextNum2:
 'Find min col:
 For col = lbndC To ubndC
 For row = lbndR To ubndR
 If Not IsEmpty(v(row, col)) Then
 colMin = col
 GoTo NextNum3
 End If
 Next
 
 Next
 NextNum3:
 'Find max col
 For col = ubndC To lbndC Step -1
 For row = lbndR To ubndR
 If Not IsEmpty(v(row, col)) Then
 colMax = col
 GoTo NextNum4
 End If
 Next
 Next
 NextNum4:
 Set RealUsedRange_Sancarn3 = Range(sht.Cells(offR + rowMin, offC + colMin), sht.Cells(offR + rowMax, offC + colMax))
 Exit Function
 URValueError:
 If Err.Number = 7 Then 'Out of memory error:
 'If out of memory, fall back on VBasic2000's version. It's not optimal but it doesn't have memory issues!
 Dim firstCell, lastCell As Range
 With sht
 Set firstCell = .Cells.Find("*", .Cells(1, 1), XlFindLookIn.xlValues, , XlSearchOrder.xlByRows)
 If Not firstCell Is Nothing Then
 Set lastCell = .Cells.Find("*", .Cells(1048576, 16384), XlFindLookIn.xlValues, , XlSearchOrder.xlByColumns, xlPrevious)
 Set RealUsedRange_Sancarn3 = .Range(firstCell, lastCell)
 End If
 End With
 Else
 'Raise unhandled error
 Err.Raise Err.Number, Err.Source, Err.Description, Err.HelpFile, Err.HelpContext
 End If
 End Function

----

Edit: `IAmNerd2000`'s original approach fails when formatting lies outside the "RealUsedRange". Thus it was removed from this post. 

----

Edit: As `MacroMarc` pointed out, very large used ranges will cause the optimal code to crash due to an `Out of memory` error. As a current work around I resort to `VBasic2008`'s code if the error occurs. So at worse it will be as slow as `VBasic2008`'s code, but at best it will be 10x faster.