Redo alignment after tip rotation?

No, as long as the probe is correctly calibrated and the part has not moved, there is no need to repeat the alignment every time you index to a new wrist angle.

Not really a PC-DMIS-specific issue, but  kinematic engagement of articulating heads is less that 100.000% repeatable; with tight tolerances, one might want to either re-calibrate/autocalibrate tip with every wrist-angle change, or, as JasonD is doing, re-establish CSY.  You can see this on high-magnification profile/roundness plots when a circle is constructed with multiple tip-angles, plot may look like a saw-blade, but not so when the auto-calibrate step is added.  Just depends on tolerances.

If you are chasing sub 0.0005" tolerances, re-measuring datums after a probe rotation will mitigate any additional variation caused by probe angle/calibration changes. 
--So it really depends on what kind of reproducibility/accuracy you are needing to quantify.   IMHO if you have 0.005" tolerances, yes it's a complete waste of time.

As Neil stated, there is no need to remeasure your alignment features.

it is best practice to try and measure as much as possible with the one tip before indexing or changing tip angles.

if you are worried about the indexing repeatability, perform an auto calibrate after each tip/index change. This is more important if you are using long extensions and are measuring parts with tight tolerances.

As louisd  stated, it depends on my tolerances for the features that I will be measuring and in most instances I will not remeasure datum features. I have hole position callouts on some parts that are a low as Ø 0.015mm on some surgical instruments and for this I am using a star probe and before I measure the hole I will touch off on the 2 datum surfaces (Y and Z) with the 90° styli that I be measuring the holes with.

Here's an example of typical error produced by a change to "B" angles without any fresh autocalibrate command after each angle change.

Tips were calibrated at beginning of program only.  

This is on a ring gauge, phantom form error stays square to machine axis, regardless of ring's rotation.

Only ways to avoid this is to A) avoid articulating wrists,  B) re-doing alignment after tip rotation, as JasonD asked, or C)  re-qualifying after each and every wrist engagement.

Is the level of error dependent on the Probe Head you have? Or does the small amount of error typically stay the same for all heads? Say for example we have the HH-AS8-T2.5.

We have the same probe head.  The error is within the wrists, and is directly proportional to distance from wrist joint to stylus.  In this case, about 285mm (110mm tip, plus probe head).  It's not really a PC-DMIS thing, just the way articulating wrists work. 

0.0005"=0.013mm, How about calibration from 9 hits to 18 hits? How much accurate It could improve?