Comment 10 for bug 79578

Meanwhile I changed my partitions for some other reason and created a boot partition too at this opportunity.

Further I found this today:
http://www.gnu.org/software/grub/manual/html_node/Stage2-errors.html
[Error] 18 : Selected cylinder exceeds maximum supported by BIOS
    This error is returned when a read is ttempted at a linear block address beyond the end of the BIOS translated area. This generally happens if your disk is larger than the BIOS can handle (512MB for (E)IDE disks on older machines or larger than 8GB in general).

So I made my system use /dev/hda3 (which is entirely below 8GB) as /boot and reinstalled grub from feisty (doing grub-install /dev/hda too) today.

Now, lets see if it happens again ...
(booted successfully by now)

My new partition table:

sudo fdisk -l

Disk /dev/hda: 80.0 GB, 80026361856 bytes
255 heads, 63 sectors/track, 9729 cylinders
Units = cylinders of 16065 * 512 = 8225280 bytes

   Device Boot Start End Blocks Id System
/dev/hda1 * 1 192 1542208+ b W95 FAT32
/dev/hda2 193 714 4192965 b W95 FAT32
/dev/hda3 715 733 152617+ 83 Linux
/dev/hda4 734 9729 72260370 f W95 Ext'd (LBA)
/dev/hda5 976 1913 7534422 83 Linux
/dev/hda6 1914 2015 819283+ 82 Linux swap / Solaris
/dev/hda7 2016 3008 7976209+ 83 Linux
/dev/hda8 3009 8575 44716896 83 Linux
/dev/hda9 8576 9729 9269473+ 83 Linux
/dev/hda10 734 975 1943802 b W95 FAT32

Partition table entries are not in disk order