Background CSS images won't be changed after reuploading & Cache flushing
Since all caching aren't able to fix, let's try narrowing down the issue.

First, try to delete the image from your theme. Flush all caches and see if the background image is still there. If it is, open your browser development tool and check the background image URL and try opening it in a new tab, check the URL of the image and follow it in your server's directory if it really still exists.

Second, try restarting the server or any related running services you have in your server.

Hope this can at least give an idea on where to find what's causing the issue.