> try to expire old pbfids (and risk breaking "legitimate" links)

Or encode some versioning scheme, and keep trying various versions until one comes up with a valid link. If we can think of these things in seconds, so can the engineers at FB.