So this has been happening to me for some time now, and while it doesn't happen THAT much, it does happen occasionally and it can put you in very bad situations.
I'm not sure how to exactly reproduce it yet, but I've been getting this bug on Ashe and MF (they're the only champions that I play with HoB anyway). And here I have a very clear clip of the bug taking place as MF:
As you can see, my first auto on Caitlyn did not give me the attack speed, and it instead created an animation where it looked like my HoB just came off of CD as I auto'd her. And in case you think it might've been down right before I auto'd her, here's an extended version in lane clearly showing me going out of combat for 4 seconds and not auto attacking a single champion prior to the Rek'Sai gank:
Went out of combat for 4 seconds several times, so HoB was 100% off of CD and ready to use. But it bugged as I attacked Caitlyn. Please fix this with the buff next patch or else many more people will experience it since the keystone will start to be taken more and more.