Where do Android apps store data that survives uninstall? TL;DR On non-rooted devices, where do Android apps store data that survives uninstall?

Backstory: I installed an Android app a couple months ago and configured it to my liking.  After a couple weeks, I no longer needed it, so I uninstalled it.  After the uninstall, I didn't see any files left behind in Internal Storage, and the device had no microSD card installed, so no files were stored there either.

To my surprise, when I reinstalled the app, it remembered all of it's configurations.  I use a firewall, so it didn't download the configurations from the cloud.

Thus, the question: On non-rooted devices, where do Android apps store data that survives an uninstall?
Apps are supposed to store their data and related files either in /sdcard/Android/data/com.app.id or /data/data/com.app.id; however, many apps (especially ones from China) don't abide by this guideline and create folders in storage individually, that store various information.

For example, apps using Aliyun SDK will generate .DataStorage, .SystemConfig and .UTSystemConfig directories under the root of the internal storage, primarily for storing device ID info. Such info can be used to identify users even if they haven't registered an account of respective apps.

As for what you described - fully-locally-stored data (no access to cloud) - it also is possible. I have one such example on my phone which is a 3rd-party app to a forum (I prefer not to disclose what exact app it is), with several features like signatures, custom ID flairs to enhance the original app. It stores all settings related to those enhancements under .db files in a folder under the root of internal storage. When the user changes device, he can just copy the folder over to the new device, and upon opening these customizations will be read and appear intact. Below shows one of the pages of its main .db file, storing key setting values (sensitive info redacted):