After having cleaned the valve and having put ca. 400 km on the car without any further errors in the ECU's memory, here's a report about what may have done the trick, at least as a somewhat temporary fix. The least thing I can say is that things have became a lot better; before the repair, the error kept coming back almost immediately.
- The best option of cleaning the valve seems to be using a variety of agents. I have changed back and forth between gasoline, WD-40 and brake cleaner. It appears that WD-40 was a particularly important member in the trio, because it doesn't evaporate right away and is able to soak into and soften the very hard and very solid carbon deposits around the critical areas inside the valve. Once the WD-40 managed to make the carbon somewhat soft and sticky, the other solvents (gasoline, brake cleaner) had a chance to further dissolve the deposits.
- It appears that it does help to electrically actuate the valve while it is being soaked in any of the three substances at a rate of approximately 1 Hz. Care must be taken because even a tiny electrical spark in the presence of evaporating hydrocarbons poses a serious fire hazard. I do not recommend doing this inside a building or garage under any circumstances, and even outside, it is wise to be very careful. Avoid loose contacts. The freewheeling spike caused by an energized coil will create significant sparks at loose contacts, and the mechanical movements of the actuated valve will further help loosen any less-than-ideal connections. Do not store any cans or jars with cleaning solvents near your set-up in order to minimize the amount of flammable liquid near the possible source of ignition. Make sure your set-up is ventilated well to keep the concentration of inflammable vapors as low as possible. Besides sparks, consider heat generated by ohmic losses in the EGR valve's coil. Be prepared for any surprise that may happen. Use at own risk. This being said, here's what I have used, starting with a schematic. If anyone's interested in building something similar, details are added at the very bottom (*):
Pictures of the quick and dirty breadboarded implementation:
... and a close-up of the valve's pins:
Opening and closing the valve repeatedly appeared to have helped knock some of the dirt away.
- However, in addition to soaking and spraying with the above-mentioned solvents, I have also used a solid copper wire and some plastic (taken from a q-tip) to scratch away whatever deposits I could reach. My hope was that the copper, being a fairly soft type of metal, did not scratch the surfaces inside the valve.
It will be interesting to see if this fix will turn out to be long lasting, but it certainly was an improvement.
(*) Circuit Description, schematic repeated for better readability:

An Oscillator around Q1 and Q3 has a frequency of approximately 1 Hz.
Even though this basic two-transistor multivibrator circuit is often called a "square wave oscillator", this is, at best, a euphemism. The signal at Q3's collector has anything but sharp, square edges:
This is why a Schmitt Trigger circuit follows, built around Q4 and Q5. Q6 takes the Schmitt Trigger's output and prepares the signal...
... to be fed into the final transistor, labeled Q8, switching the output from 0 V to 12 V and back again...
... driving the solenoid:
In case anything should go wrong (read: shorted output), there's a current limiter built with R15 and Q7 allowing a maximum load current of approximately VBE, Q7 / R15 = 0.65 V / 0.22 Ω = 3 A - enough for most automotive solenoids or relays to be tested, but also low enough so Q8 has a chance to survive the mis-connected output leads.
All transistors except Q8 can be any small signal jellybean parts, e.g. BC546/BC556 (for Europeans), 2N2222/2N2907 (for Americans) or 2SC1815/2SA1015 (for Asians) - if you're old enough to remember the now somewhat obsolete tradition of designers from the respective areas to use EECA-, JEDEC- or JIS-labeled parts. The output transistor, Q8, should have a rating of well above 1 A and at least 40 V, so a TIP31 or 2SC1061 or pretty much any other comparable transistor in a TO-220 package with a small heat sink will do just fine. R12 needs to be somewhat bigger because it dissipated quite some power. The reason for its low value (150 Ω) and the resulting, comparatively high current is the low beta of the output transistor. We need sufficient base drive from Q6's collector through R12 into Q8's base.
The freewheeling diode, D1, should be fast and have a rating of at least 1...2 A and 60 V. My particular EGR valve does not have the diode integrated. If this would be the case, one would have to be careful about the polarity when connecting the valve's solenoid to the test circuit, of course.
Yes, there are of course many more options of building a circuit like this (555 timer!), but for the fun of it, I made up this design using single transistors only.