Jesse, you have some great responses below. So great question to begin with. I also like the 4 example scenarios you posted. What I'd like to ask is, what percentage of their business is driven directly/indirectly from their websites ?
Once you know how much money a business generates from a website, you can then put some sort of an ROI and budget you are willing to spend to expand on to that. Now, the question is, would you list your business in BBB if there was no SEO value ? Let's say we go back in 1996 when Google does not exist. You have Altavsita, Dogpile, Excite.com and so on. They don't look at the BBB listings. They only look at the Meta Data. Would you still list yourself ? If you'd say yes then, I'd say yes today. If it was no then, let it be a no today.
However, if you are also struggling with some rankings and looking for some brand citations etc, you might get listed and move on. It's not really going to move the dial. Don't expect that you list today and in X amount of time, your rankings improve.
I don't know if I helped you or confused you further. Just my 2c, for whatever it's worth 