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

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.