Did you switch off the system and switch on again?
Yes

Did you check the BIOS settings. e.g. USB Settings?
Yes, boot order is USB first.

Does it say USB HDD in the BIOS boot menu?
This is the interesting part, it doesn't say when the usb key is plugged into the usb 3.0 port. Looks like BIOS do not detect/see a usb hdd on usb 3.0 port ... but only for my new 64G usb key. The older 16G usb key was booting fine from that same usb 3.0 port.

Is the first partition marked as Active (boot flag)?
No.

Did you install grub4dos to both PBR and MBR?
I don't know, I just run the fmt.sh script.

Latest BIOS version is A16 25th Oct 2016 with improved USB support. Do you have this?
I only have A15.

I also tried to format the usb key using Windows instead of linux. This is the latest fdisk output after Windows format:

sudo fdisk -l /dev/sdb
[sudo] password for lvu:
Disk /dev/sdb: 57.8 GiB, 62087233536 bytes, 121264128 sectors
Units: sectors of 1 * 512 = 512 bytes
Sector size (logical/physical): 512 bytes / 512 bytes
I/O size (minimum/optimal): 512 bytes / 512 bytes
Disklabel type: dos
Disk identifier: 0xfc5ed0c2

Device Boot Start End Sectors Size Id Type
/dev/sdb1 * 63 121242491 121242429 57.8G c W95 FAT32 (LBA)
/dev/sdb2 121242492 121242554 63 31.5K 21 unknown

Still the same behavior (usb 3.0 port do not boot) with formatting using Windows. However at least usb 2.0 port stop staying "invalid partition table!".

I guess a new BIOS might be the fix. At least now the usb 2.0 port boots properly so I have a fall back. I'll reply my findings if I feel brave enough to update the BIOS. I got burned once in the past updating BIOS.

Thanks for all the help. Looks like formatting on Windows does a more complete job than Linux. Is it because Linux is lacking any functionality or you just didn't get around to have feature parity between Windows and Linux?

I am still puzzled as to why my older 16G usb drive was working fine on that same usb 3.0 port although it was formatted on Linux.