static void
show_agp(struct device *d, int where, int cap)
{
  char rate[8];
  ...
  format_agp_rate(t & 7, rate, agp3);
  ...
}

calls

static void
format_agp_rate(int rate, char *buf, int agp3)
{
  char *c = buf;
  int i;

  for(i=0; i<=2; i++)
    if (rate & (1 << i))
      {
	if (c != buf)
	  *c++ = ',';
	*c++ = 'x';
	*c++ = '0' + (1 << (i + 2*agp3));
      }
  if (c != buf)
    *c = 0;
  else
    strcpy(buf, "<none>");
}

when a system has AGP1 _and_ AGP2 _and_ AGP4 support, the for loop will make the
following string: 'x1,x2,x4'. That all fine. But
*c++ = '0' + (1 << (i + 2*agp3));
Leaves *c at position 9, and then this code:
  if (c != buf)
    *c = 0;
Assigns the ninth position: c[8] = 0, to zero terminate the string...
That's when the overflow happens...

Please try out the included patch:
--- lspci.c     2002-12-26 21:24:50.000000000 +0100
+++ lspci.c.fixed       2004-07-26 02:34:14.000000000 +0200
@@ -432,7 +432,7 @@
 show_agp(struct device *d, int where, int cap)
 {
   u32 t;
-  char rate[8];
+  char rate[9];
   int ver, rev;
   int agp3 = 0;

Apply the patch with patch -p0 < lspci.diff inside the pciutils-2.1.11 directory.

This bug was found and fixed by Pascal de Bruijn with assistance from Rene van Rijsselt.
Thanks to solar on irc.freenode.net#gentoo-hardened for pointing me in the right
direction.