Same Creature, Different DC
Disclaimer: For the purposes of this answer, we're going to assume that reincarnation converts the old body into an object instead of a creature (or both, which is what my opinion on them is), and that any connections with the old body by the creature are lost. This is because, if the old body still has a connection to the creature, it raises a number of nebulous questions such as, if they die, can both bodies be used to bring them back to life? Would their stats and abilities change based on which body was raised? And so on. While a campaign where the BBEG has a myriad number of bodies stored in various places of all different types from reincarnating over the years could be interesting, for simplicity's sake, we're going to ignore the possibility of this for this answer.
A creature affected by the reincarnation spell is still the same creature, that's why the spell only affects racial abilities (and even then, not all racial abilities either), and not abilities learned from training through classes. Followers from leadership, animal companions, familiars, etc. continue to be connected to them even though they just switched bodies. Basically, there are many things that are tied to the creature's soul rather than their specific body.
Similarly, the villain isn't scrying Bob's old body, they're scrying Bob. Therefore Bob would get a will save as per normal for the spell, but if the spell succeeded, it would show his current body, not his old one. As for his adjusted appearance, it would not be apparent to the villain that they've reincarnated, when there also exist a myriad number of polymorph spells.
Now, since the will save for Scrying depends on a couple of other factors, the DC should be adjusted accordingly:
- Did the villain meet Bob in person before and was using the firsthand will save modifier? They don't really have a proper firsthand impression of him still, as a GM I would use the secondhand DC modifier instead (+5).
- What sort of a physical connection did they have to Bob? If they were using bits of Bob's old body or a picture/likeness for the connection previously, I wouldn't count that anymore. If they were using a possession or garment, it's still something that belongs to Bob, so that connection still exists.
To sum it all up, Scrying still targets Bob, but the DC needs to be adjusted appropriately to the new situation.
On the Subject of Souls and Divination
For some more details on scrying and souls, and what not, a good tidbit is hidden away in the Possession Rules from Occult Adventures (emphasis mine):
Possession does nothing to obfuscate or block most divination spells. For example, if an evil mesmerist is possessing a paladin, detect evil will sense the presence of an evil creature when the paladin’s body enters the area of effect. The Hidden Presence feat can assist a possessing creature in foiling divinations. If a creature’s body and soul are in two different locations, as in the case of a caster of magic jar, divination spells that depend on location, such as locate creature or scrying, fail to produce results. The exception is discern location; this powerful spell provides both locations unless the body and soul are protected by mind blank or a deity.
This tidbit indicates that what scrying targets (in contrast to my answer above), is both the creature's body and soul, and that both need to be in the same location for it to work.
Now before anyone starts pointing out how the old body relates to this situation, and that it being separated should stop scrying:
- Possession is a radically different situation where the soul is out of the character's body for a short-term period of time. They still have a body they need to return to later.
- Read the disclaimer. Connections, gone.
- There are a number of ramifications to that ruling. Not the least of which is that doing such grants permanent immunity to scrying by those who reincarnate, even if the scrying creature has only ever met and interacted with the current body, and is attempting to scry on the current body.
Therefore, it's safest (and simplest) to say that the old body doesn't count as something that would be scryed upon, and that only the locations of the current body and the soul matter.