It seems that not the size of the partition was the cause of my problems. I did some more testing and extended the partition to 10GB, later to the maximum of the card (16GB) and I was able to boot into recovery.
The only guess I have is the partitioning of the SD card. First I did a format from the readers initialization menu. Later I deleted the whole partition with 'Minitool Partition Wizard' and created a new one. Maybe it was just a problem with the default partition scheme.