This is the solution I found. I have tested it thoroughly several times, and I have been using the resulting font in a number of places for over 2 years now, but be warned: some parts of the procedure may be anywhere from suboptimal to plain wrong.

Before you ask "why don't you make the resulting font available", the answer is: "because I'm not sure I can do so". Font copyright is an intricate matter.

Download the corrected Fixedsys Excelsior font (file FSEX301-L2.ttf, at comment #16)

Install FontForge (e.g., from the Ubuntu Software Center)

Right-click on the FSEX301-L2.ttf file and open it with FontForge. In the Load Bitmap Fonts window that appears, click on No.

Click on File → Execute Script..., and copy&paste the following into the window that appears:

SelectAll()

foreach

   if (GlyphInfo("Width") != 80)

      DetachAndRemoveGlyphs()

   else

      b = GlyphInfo("BBox")

      if (b[0] < 0 || b[1] < -30 || b[2] > 80 || b[3] > 130)

         DetachAndRemoveGlyphs()

      endif

   endif

endloop

SelectNone()

Then select FF and click OK (it will take a while, you will have to wait until the Execute Script window disappears)

Click Element → Font Info... In PS Names change the Fontname, Family Name, and Name for Humans, e.g., by appending Mono (spaces are allowed only in the second and third string).

In the same Font Information window, select OS/2.

In the Misc. tab change the PFM Family to Monospace.

In the Metrics tab, set Win Descent Offset and HHead Descent Offset both to 0 ^(*).

In the Panose tab, change Proportion to Monospaced.

In the same Font Information window, select Lookups.

In the GSUB tab, and in the GPOS tab, select each line in turn and click Delete.

In the same Font Information window, click OK, and in the Change UniqueID? window that appears click Change.

If you want, you can tweak one or more questionable features of Fixedsys. E.g., the zero character is shifted one pixel to the right. To shift it back to center, double click on it, then click Metrics → Set LBearing..., set the LBearing to 10 and click OK. You can also change the shape of characters, but always keep control points at multiples of 10, and the width at 80.

Click Element → Bitmap Strikes Available..., then, in the window that appears set Pixel Sizes to 16 and click OK.

Click File → Generate Fonts..., choose a different directory and/or a different filename if needed, make sure the output format is TrueType, and click Save. In the Non-standard Em-Size window that appears click Yes. In the Errors detected window that appears next click Save (don't worry).

Quit FontForge (File → Quit). In the Font changed window that appears click Don't Save.

Move the generated file to the .fonts subdirectory of your home directory (create it if it doesn't exist).

Open the Gnome Terminal. Click Edit → Profiles... In a profile (I suggest you create a new one) change the font to Fixedsys Excelsior 3.01-L2 Mono (or whatever you have called the mono version of Fixedsys Excelsior), at size 12 (which is the only "true" Fixedsys size). If you want, you can also disable bold text. I suggest black text on white background, but that is a matter of taste.

The bold variant of this font is equivalent to repeating the character shifted by one pixel to the right (this is different from FSEX301-L2.ttf, where it appears smoothed). It is not very legible - but do you really need bold? I don't. The problem is only with those contexts where bold cannot be disabled (not even, e.g., by editing syntax highlighting), especially in those cases where the character spacing is incremented by one pixel as well, breaking alignments (this is not the case in gnome-terminal). I haven't found a solution to this last nuisance yet. Suggestions are welcome.

(*): not needed since the FontForge release of 2012-07-31 (in 14.04 LTS - Trusty Tahr)