Iphone does the same thing when the media volume is set above the "safe" limit.
It's a regulatory requirement not some Android bug.
The user can choose to override the limit so that the sound level can be increased up to maximum 100dB. If the user overrides the limit, warnings about the risks must be repeated every 20 hours of listening time. "
via http://www.bbc.com/news/health-21294537
The "repeated every 20 hours" would explain why OP was seeing the warning seemingly randomly.