Matrix’s encryption algorithm was broken for a while and when it was fixed it it took app devs years to migrate to the new requirements. It still might even be the case for a lot of them, I haven’t looked in a while.
SimpleX should be secure AFAIK though, but I’ve heard that it may not be able to scale well to larger user bases. It seems everything has pros and cons.
I would say it’s likely related to ColorOS or Play Services (or both) tracking something behind the scenes and feeding it to your ad profile. You’ve done a lot to try to reduce your fingerprint but it sounds like it could be something harder to track down.
Have you considered switching to another version of Android that uses microG to reduce Play Service permissions or another phone with GrapheneOS? That may be the next option unfortunately.

Fair points. I’d say it depends on what we’re focusing on.
Maybe a good compromise would be to have the account that sent the message generate the preview. At least that way you’d maintain E2EE and save the webserver some unnecessary demand.
I can also see how this could be less reliable (because we’re now relying on a client with all sorts of variables) and less safe (malicious sender could mask malicious links with benign previews) than the server method but it all depends on which you prefer more.
After thinking about it in this situation, previews are just a nightmare to deal with privately and I’d probably just want to turn them off.
That’s if you are using a file to store additional data. Also JPEG and other lossy formats can have all sorts of artifacts that may (depending on the size of hidden data) seem typical.
What I thought they were referring to was encryption at the filesystem level which doesn’t require file blocks to be contiguous, allowing blocks to be interlaced with the hidden data.