Hi,
I've received help from some nice guy on #debian-boot
The problem is in all likelihood linked to this strange partition layout shown by parted.
Anyway, here's the trick I used to solve my issue:
1- format my USB stick using a GPT partition table
2- create a single vfat partition of type ef00 spanning the whole USB stick (I've used gdisk to be able to set the partition's type)
3- mount the partition
4- mount the debian iso
5- copy all files from the debian iso to the partition (taking care to also copy the ".disk" folder), while ignoring the several warnings that some symbolic links can't be copied
6- unmount the partition
7- use the USB disk to install debian on my new hp laptop
That's it.
So, my issue is solved: You may do wathever you like with this bug report now.
Thanks to the folks on #debian-boot for the assistance.
Cyrille