In Durham, we stayed with our friend Debbie Wong (no relation to the Debbie Wong Restaurant in West Springfield, MA). We call her "Little D." She took us to Bullock's BBQ for lunch. Here are Little D and Nicole in front of Bullock's.
A few web pages and alt.food.barbecue responses pointed us toward Bullock's. And it's quite well known among the locals.
We got chopped pork sandwiches. They were good but not great...just how Little D told us it would be. Flavorful, but not all that smoky. The sauce was very vinegary. There was too much sauce mixed in the with meat, as we tasted too much vinegar and not enough pork. Definitely not in the same class as the Lexington Six-Pack, although this is eastern NC style, whereas Lexington is western NC style.
The Brunswick stew was OK.