Very unusual, but not unheard of, with labs*...I'd still try going to see another vet to make sure there isn't a medical reason...anything going on with him when you're not around, e.g. other dogs, kids, something that could be bugging him?
*we've got three labs now, in a long line of labs..we've seen others with problematic labs, but they generally have had issues right from the get go.
What does the trainer think?