OK, to update my earlier post...
I unplugged all four of my plugs and took them to one room, so that I could monitor all four at once. I would recommend doing this when setting up the encryption, because the process took about two seconds when the plugs were near each other. When I had them in different rooms (on different floors, actually), it took quite a while -- and I have less confidence now that, even though the units reported success, all went completely smoothly.
So, I had them in the four corners of the same room. Then I started out by pressing the encryption button on each of them for over 10 seconds. (Hold the button until you see the lights change, something like a reset.) At this point, each of the units had a random and (unless I was very unlucky) different password. (All of the middle, "connected", lights were off.)
Next, I paired two of the plugs. Do this by pressing the power button on the first for ~2 seconds ("more than one but less than three", according to Belkin), and then the same with the second. It seems to me (although this isn't documented) that you can tell which is considered first and which second by the speed at which the "setting up encryption" light flashes: the first is slower; the second rather rapid. After a few seconds, these two units will be paired (the middle light will be on).
If you have more than two plugs, do the previous step again, using one of the already connected plugs as the first and the new one (currently with the random password) second.
After doing this, I put all plugs back in their proper homes. I've since been monitoring the connection between my PC (upstairs) and my router (downstairs), and, over about three hours, things have been perfectly stable (no dropouts). I don't know why setting up the encryption afresh (and with the units in close proximity) should have made a difference, but it seems to have done. Of course, three hours isn't exactly a very long test, so we shall see...