The 2nd picture doesn't show the option to Browse to a helper app, maybe because the attachment isn't properly encoded. I sent myself an mp4 attachment with TB, and the open dialog sequence is shown in the attached pictures (TB 128/W11). As you can see in the 3rd picture, there is a Browse button to choose any app.

See if you can reproduce the process and define VLC as the helper app. Check 'Do this automatically...' to save in Settings.

I was able to open a .mp4 file attached to an older email. As you can see on the attached screenshot, VLC is an available option. So, as you suggest, the problem may lie in the problem mp4 file. However, I was able to view the file after saving it and then opening it with VLC.

Also, I should mention that I upgraded my Ubuntu to Ubuntu 24.04.1 LTS from version 22. Perhaps Ubuntu 24 is fussier.

Would you like me to send the troublesome .mp4 file to see if there is anything that can be learned from it?

I wouldn't know how to analyze an mp4 file, but the issue remains that you can't select any app that isn't on the list in your picture. All I can suggest is you run in Help/Troubleshoot Mode in case there is something causing the dialog to be incomplete. It might also just be an artifact of the version of TB for your version of Linux.