But what if I want to iterate over the Foo pointers in my graph? I suppose one way is this:

for (int i = 0; i < num_vertices(g); i++) {
Foo *foo = g[i];
}

Yup.

But I assume this wouldn't scale if I were to use listS instead vecS. Also, I'd want to use a proper vertex_iterator anyway, so I can grab all the properties I want in one loop. But how can I access my Foo pointer from the vertex_iterator? I've looked though the docs and sample code but I just can't figure it out.

Pretty much the same way:

typename graph_traits<G>::vertex_iterator i, end;
for(tie(i, end) = vertices(g); i != end; ++ii) {
Foo* f = g[*i];
}

Dereferencing a vertex iterator returns a vertex descriptor. The same is true for edge iterators and edge descriptors, if it comes up.