Long story (and quite a few checks, verifying code, ...) short:
it was a very stupid issue. But one that can occur if you don't think twice about your datasource query. Browsers have a maximum length for their url :)
I was using Chrome which allowed me to have the url just a bit longer than the Edge my customer is using. That's why they saw it sooner..
What happened: the customer started adding folders, and my query detected those. All seemed fine, until they had too much folders and the request broke. Sitecore sends a request that contains all the guids of items that can be a parent. In ur case this turned out to be something like this:
/sitecore/shell/default.aspx?xmlcontrol=Sitecore.Shell.Applications.Dialogs.SelectRenderingDatasource&hdl=262D2DC610BF40EE95506031CCDD3DCB&ro=sitecore%3A%2F%2Fmaster%2F%7B5B1E7DFB-3AB8-44B9-8AC6-CB6852204223%7D%3Flang%3Den%26ver%3D1&fo=sitecore%3A%2F%2Fmaster%2F%7B5B1E7DFB-3AB8-44B9-8AC6-CB6852204223%7D%3Flang%3Den%26ver%3D1&sr=1&ic=BusinessV2%2F32x32%2Fcabinet_open.png&txt=Select%20the%20content%20that%20you%20want%20to%20associate%20with%20the%20rendering%20and%20use%20as%20the%20data%20source.&ti=Select%20the%20Associated%20Content&bt=OK&rt=Id&dsDN=Documents&dsRoots=sitecore%3A%2F%2Fmaster%2F%7B5B1E7DFB-3AB8-44B9-8AC6-CB6852204223%7D%3Flang%3Den%26ver%3D1%7Csitecore%3A%2F%2Fmaster%2F%7B74784153-B752-481B-9127-D4186D4B847A%7D%3Flang%3Den%26ver%3D1%7Csitecore%3A%2F%2Fmaster%2F%7BDDE0D7D1-F9CF-448E-BD98-287A59324996%7D%3Flang%3Den%26ver%3D1%7Csitecore%3A%2F%2Fmaster%2F%7B3EE8366B-7469-4F7D-8F4B-5C9D1ECEAE35%7D%3Flang%3Den%26ver%3D1%7Csitecore%3A%2F%2Fmaster%2F%7B54335C0F-C283-4EE6-B5DE-95D1A56CC52D%7D%3Flang%3Den%26ver%3D1%7Csitecore%3A%2F%2Fmaster%2F%7B158080F7-EFDF-46D4-8BAE-6906D0DD9540%7D%3Flang%3Den%26ver%3D1%7Csitecore%3A%2F%2Fmaster%2F%7B19A6DE86-7FAF-4861-84E8-ECD4997CB18C%7D%3Flang%3Den%26ver%3D1%7Csitecore%3A%2F%2Fmaster%2F%7B3ADF864C-E605-4690-8C60-C0CCA6CEFF6C%7D%3Flang%3Den%26ver%3D1%7Csitecore%3A%2F%2Fmaster%2F%7B28EF1B1D-57A1-446D-BD78-A2EA7145A936%7D%3Flang%3Den%26ver%3D1%7Csitecore%3A%2F%2Fmaster%2F%7B1B8BCF62-57E6-46F2-A1BF-DCE40A14D0CD%7D%3Flang%3Den%26ver%3D1%7Csitecore%3A%2F%2Fmaster%2F%7B9FEA26FA-52B7-46F3-BBCA-4BE85A138707%7D%3Flang%3Den%26ver%3D1%7Csitecore%3A%2F%2Fmaster%2F%7B07AB8027-1C67-4EA0-81A7-FA04409FDE4F%7D%3Flang%3Den%26ver%3D1%7Csitecore%3A%2F%2Fmaster%2F%7B0BC1A62E-3006-44DF-890D-550099C3ECEB%7D%3Flang%3Den%26ver%3D1%7Csitecore%3A%2F%2Fmaster%2F%7B44978BEE-B96A-498E-93DB-867BF97FFCA3%7D%3Flang%3Den%26ver%3D1%7Csitecore%3A%2F%2Fmaster%2F%7B9700DC24-8969-4638-ACC3-34D54335829E%7D%3Flang%3Den%26ver%3D1&clang=en&cip=...&r=%7bD86F7730-C038-43C9-8992-4A4B60DADCE1%7d
And this went over the browser limit (2083) - what caused the 404. And the error.
We fixed it by changing the datasource location query to limit the list of 'parents' - which was possible as our query was not specific enough.
Lesson learned:
When you define a query for a datasource location, make sure the result cannot
contain too many items.