Fixed with grml-rebuildfstab 0.4.4.

Further info:

# fdisk -l /dev/sdb

Disk /dev/sdb: 8086 MB, 8086618112 bytes
249 heads, 62 sectors/track, 1023 cylinders
Units = cylinders of 15438 * 512 = 7904256 bytes
Disk identifier: 0x0009e1e0

   Device Boot      Start         End      Blocks   Id  System
/dev/sdb1               1         506     3905783    6  FAT16
/dev/sdb2   *         507         784     2145882   83  Linux
/dev/sdb3             785        1023     1844841    5  Extended
/dev/sdb5             785         809      192944   83  Linux
/dev/sdb6             810         872      486266   83  Linux
/dev/sdb7             873         897      192944   83  Linux
/dev/sdb8             898        1023      972563   83  Linux

# for i in {1,2,5,6,7,8} ; printf "/dev/sdb$i = $(vol_id -l /dev/sdb$i)\n"
/dev/sdb1 = datastore
/dev/sdb2 = grml
/dev/sdb5 = home-rw
/dev/sdb6 = live-rw
/dev/sdb7 = GRMLCFG
/dev/sdb8 = TESTSTUFF

# fdisk -l /dev/sdc

Disk /dev/sdc: 320.1 GB, 320072933376 bytes
255 heads, 63 sectors/track, 38913 cylinders
Units = cylinders of 16065 * 512 = 8225280 bytes
Disk identifier: 0xd6adc55d

   Device Boot      Start         End      Blocks   Id  System
/dev/sdc1               1       38175   306640656    b  W95 FAT32
/dev/sdc2           38176       38783     4883760   83  Linux
/dev/sdc3           38784       38913     1044225   83  Linux

# for i in {1..3} ; printf "/dev/sdc$i = $(vol_id -l /dev/sdc$i)\n"
/dev/sdc1 = MIKAUSB
/dev/sdc2 = USBROOT
/dev/sdc3 = GRMLCFG

I could get debugging info:

+ for p in '$partitions'
+ addinfo=           
+ fs=                
+ mountpoint=        
+ '[' -n '' ']'      
+ '[' -n '' ']'      
+ '[' -z '' ']'
+ check_for_label
+ '[' -x /lib/udev/vol_id ']'
++ /lib/udev/vol_id /dev/sdc1
+ PARTINFO='ID_FS_USAGE=filesystem
ID_FS_TYPE=vfat
ID_FS_VERSION=FAT32
ID_FS_UUID=4862-215E
ID_FS_UUID_ENC=4862-215E
ID_FS_LABEL=MIKAUSB
ID_FS_LABEL_ENC=MIKAUSB'
++ awk -F= '/ID_FS_LABEL=/ {print $2}'
++ /lib/udev/vol_id /dev/sdc1
+ label=MIKAUSB
+ case $label in
+ case $PARTINFO in
+ '[' -n MIKAUSB ']'
+ part=LABEL=MIKAUSB
+ addinfo=' # /dev/sdc1'
++ awk '-F ' '{s[$NF]++}END{for(i in s)if(s[i]>1)print s[i], "labels " i}' /tmp/
tmp.yOtRM0YvOG
+ warn='2 labels GRMLCFG'
++ awk '{print $3}'
++ echo 2 labels GRMLCFG
+ expr GRMLCFG = MIKAUSB
+ '[' -z '' -a -z 1 ']'
+ fs=auto
++ uniq
++ fstype /dev/sdc1
+ scanfs=vfat
+ '[' -n vfat ']'
+ fs=vfat
+ '[' vfat = swap ']'
+ '[' vfat = auto ']'
+ echo LABEL=MIKAUSB '' 'vfat # /dev/sdc1'
LABEL=MIKAUSB  vfat # /dev/sdc1

Looks like the reason for the problem is the duplicated LABEL.

Under some certain conditions there might be entries like the following in /etc/
fstab (the "/mnt/..." option is missing):

# Added by GRML
LABEL=TESTSTUFF ext3 # noauto,user,dev,suid,exec 0 0 /dev/sdb8
# Added by GRML
LABEL=MIKAUSB vfat # noauto,user,dev,suid,exec 0 0 /dev/sdc1

This does affect only *new* generated entries - so definitely no data damage. 
But there seems to some race condition on any stage between "plugin new device -
> scanpartitions/rebuildfstab -> /etc/fstab".