When you press the Delete key to delete a file, the file is permanently deleted immediately.

First determine where the file is stored. Windows does not send deletions from network shares or many removable devices to the local Recycle Bin. Create a disposable text file on Desktop and press Delete once. If it reaches the Recycle Bin, the original storage location is the boundary; use that service’s recovery or backup instead. If the desktop test is also permanently deleted, open Recycle Bin Properties and verify the option for the C: drive, because Recycle Bin configuration is per volume. Check that the Shift key is not stuck, because Shift+Delete requests permanent deletion. Then run Microsoft’s File and Folder troubleshooter and retest. Avoid deleting important data meanwhile. For anything already lost from a local drive, minimize writes and use Windows File Recovery, saving recovered files to a different drive. Recovery from a network share or cloud location must use that service’s backup or recycle system.

Recycle Bin Properties keeps a separate setting for each drive rather than one global switch, so the thing worth confirming is that the drive you checked is the drive the file was actually sitting on. If it is, then the setting really is ruled out, and there are two other things that produce exactly this.

The first is a Windows policy called "Do not move deleted files to the Recycle Bin". It does the same job as that checkbox but it's a separate switch, so Recycle Bin Properties can look completely correct and deletes still skip the bin. You'll find it in the Local Group Policy Editor under User Configuration > Administrative Templates > Windows Components > File Explorer, or if your edition doesn't include that editor, look for a NoRecycleFiles value under HKCU\Software\Microsoft\Windows\CurrentVersion\Policies\Explorer. If it's set to 1 there, that's your answer, and it would explain every drive at once rather than just one.

The second is where the file lives. Deleting from a network location generally doesn't use the Recycle Bin, so those go straight out. And if it's a OneDrive file that's still online-only, there's no local copy to move anywhere, so Windows removes the placeholder and the file turns up in the OneDrive recycle bin online instead of yours.

The Recycle Bin option and capacity have already been checked, so first confirm whether this happens in a normal local folder. Create a small test text file in C:\Users\Public\Documents, select it, and press Delete. Also check that Shift is not being held or stuck; using the On-Screen Keyboard for one test can rule that out, because Shift+Delete bypasses the Recycle Bin.

If the test file goes to the Recycle Bin, the original location is the important clue. Check the full path in File Explorer. Files deleted from a network share do not use the local Windows Recycle Bin, and removable, compressed, cloud-synced, or application-managed locations can have different deletion behaviour. 

If a test file on C: is also deleted immediately, open Recycle Bin Properties again and select C: itself in the list; the setting is stored separately for each drive. Then restart File Explorer from Task Manager: select Windows Explorer and choose Restart.

As a last step, after restoring or copying out anything currently in the Recycle Bin, rebuild its C: drive data. Open an Administrator Command Prompt and run:

rd /s /q C:\$Recycle.Bin

Restart Windows afterwards. This clears the existing contents of the C: Recycle Bin, so it should not be used until anything important there has been recovered. If files have already been permanently deleted, avoid saving more data to that drive and check backups or cloud version history first.