This is down to how the url router in Joomla 4/5 works. It needs a menu item of the category to be able to generate correct sef urls for articles.
I recommend you report an issue in the Joomla issue tracker.
So what you're saying is: for every J3 website with articles anywhere that you upgrade to J4, the URLs to the articles will change because of the new structure of J4. So in this case we need to create more than 400 redirects to redirect people from Google to the right pages?
I am saying:
For every J3 website that you upgrade to J4, direct links to articles will get different url.
A Joomla issue (or thing). Not an Articles Anywhere issue.