How can I fix this error since this makes the site nearly unusable. I am testing Netlify for hosting a larger project and if I cannot fix this I will likely use Vercel since it supports next.js well.
No, the latest deploy is with an older version of the next.js plugin. Anything before version 4.0 works. Currently I am using 3.9.2. This further enforces my assumption that this is caused by the redirects placed. Is there any reason the images would work with the preview domain, but not the custom domain. I can redeploy with version 4.34 of the plugin if you would like to take a look.
All those redirects are required and working as intended for a major chunk of Next.js sites on Netlify. Version 3 of the plugin has been deprecated for a long time now and should not be used at all for Next 12+. There would be something specifically wrong with your setup and usage of the plugin that would be causing issues.
For the linked deploy: Netlify App, the images are failing due to error 500 which has nothing to with redirects. It is expected to see that error when you deploy using CLI, unless you install CLI on an Ubuntu machine.