At first moving or resizing a window sounds like an easy, common task. Just use wmctrl or something. Unfortunately, all command-line tools I have tried so far only work as expected if I manually moved or resized window after unmaximizing it, or if the window was never maximized (I use KDE4).

This is the easiest way to reproduce my problem. First, get Window ID ($WID) by running "wmctrl -l" for some maximized window. Then:
For me, wmctrl unmaximizes the window successfully but for some reason cannot change its position or size afterwards. Only way I have found to get the second command working is to move/resize the window manually. Otherwise, the window will ignore attempt to change its geometry (like it was still maximized).

This problem seems to be not specific to any particular tool. For example, xdotool also fails to change window size/location if the window was just unmaximized but was not moved/resized manually after that.

Is there reliable way to set window geometry even if the window is currently maximized? Obviously, just unmaximizing it is not enough.

Workaround was suggested by n.m. from stackoverflow. The following example should work even if the window is maximized:
However, it is unclear why unmapping and mapping is necessary for freshly unmaximized window. This seems to be true for all command-line tools and window managers. Perhaps this is a feature, but feels more like a bug.

I THINK (not certain) this a window manager operation - the window is tagged with the hint "MAXIMIZED"... so it ignores size changes other than through the mouse (and some window managers even ignore that, but most of those are no longer used). Unmapping a window removes all window attributes, then mapping it back allows for a resize (the MAXIMIZED hint was removed by unmapping).

This could be considered a bug, but it also could be considered a feature as the user did indicate that the window was to be MAXIMIZED.

I think you misunderstand. The window WAS maximized, but it is NOT anymore, it is unmaximized (either manually or programmatically). All normal window managers allow you to move unmaximized windows with a mouse, otherwise it would be impossible to move windows with a mouse.

This depends. For example if I run:
There two possible outcomes: if I keep mouse cursor on the same monitor, the window will reapper maximized if it was maximized, but it will reappear unmaximized if I move mouse cursor to other screen. This is why it's necessary to explicitly unmaximize the window for reliable result, unmapping/mapping by itself is not enough.

But it wasn't to be maximized. Let's say I have maximized window $WID. If I execute "xwininfo -wm -id $WID" I get:
Now if I run "wmctrl -i -r $WID -b remove,maximized_vert,maximized_horz" and then xwininfo -wm -id $WID" again I get:
Note that there is no "Maximized" states anymore, and "Window state:" is not printed anymore because all states were removed. But if I try "wmctrl -i -r $WID -e 0,$x,$y,$width,$height" it will do nothing. So I move the window manually a bit and try the command again. Now it works and resizes/moves the window.

Let's try that again but record more info in attempt to find out what happened. I maximize the window again, now unmaximize it. I record all info I can get about current state of the window using "xwininfo -all -id $WID > /tmp/unmaximized-stuck". If I try to move/resize the window programatically now it will be stuck. I resize the window manually a bit, and then set its size exactly as it was before (it does not matter programmatically or manually). I record its current state again: "xwininfo -all -id $WID > /tmp/unmaximized-not-stuck". Then I try to find out what's the difference between "programmatically stuck" window and normal window:
It turns out that both files are exactly the same, so there is seems to be no difference, but that can't be right. In both cases we had unmaximized window of the same size in the same location but in the first case the window couldn't be moved programmatically and in the second could, so there must be some difference. Very strange.

What you are saying about unmapping and mapping clearing some window attributes makes me think that some other unknown window property (so definitely not "maximized vertically" or "maximized horizontally") exists, perhaps it's undocumented, which does not allow freshly unmaximized window to be moved/resize programmatically, and it is removed by unmapping and mapping (or manual move/resize). But I have no idea how to find it, because xwininfo -all does not show it. Unmapping and mapping again is just a workaround for unknown problem, so any help or ideas how to find this unknown window property would be appreciated. Perhaps somebody knows a way to get more info about X11 window than xwininfo -all can give?

Ever since developers depreciated the use of xresources (IMO stupid) it has been impossible to get the information about windows.

This is a window manager function - and most window managers no longer provide that information through the normal channels.