Solving WordPress unable to upload media – another way

Working with Wordpress installations all the time, I get to encounter the weirdest issues. One of theme is the all-known “unable to upload media”, translated by Wordpress to a clear and yet useless message.

First step is, naturally, to check permissions. But what do you do when permissions are perfect, and yet Wordpress can’t upload?