The question is really clear.
Which (Windows-) folders always have write permissions?
So I need to find a folder which always has write permissions on any system for any application.
Currently I used %AppData% but I got notifications from some users that the path had no write permissions (especially on public computers).
Which folders are writable depends on not only the OS but also the security/guarding system installed on that computer. Some anti-virus software, or system admins, can install/create very restricted data access policies on computers. For a public computer, most likely %TEMP% folder might be the only common writable folder. Without writing access to temp, many applications won't run at all. Of course, you can't expect data will be saved permanently under temp folder.
The second hopeful place will be user's local data folder, normally AppData/Local, if you don't need to consider roaming data. Again, it depends on what kind of access restriction on that computer.
See this link about Windows appdata folders.
https://msdn.microsoft.com/en-us/windows/uwp/app-settings/store-and-retrieve-app-data