I was supposed to get mine two days ago. This is based on my NCSoft account showing that it was created on May 15, 2004, and my recollection that I played CoH for the first time on a Saturday (which May 15th was in 2004.)
Now it's May 17th, and still no 5-year Veteran badge for me! Even if I'm not remembering correctly, and I actually starting playing the game on Sunday the 16th, that's still earlier than, you know, May 17th.
For now, I'm going to write it off as the badge just doesn't kick in on a weekend (although, the 15th was a Friday,) and I'll have my badge after tomorrow's Monday Maintenance. If I don't have it after that, then complaints will be submitted. Full travel power at Lvl 6 is too good to not raise a ruckus about!