It essentially renders the part(s) useless, since one can't precisely time a firmware loop

Well, if you really want to count cycles to achieve synchronization, then any part with caching might be useless for your application.

I'm having some major headaches here with this concept due to a communication protocol that was once designed to be handled by 16 MHz 12-clockers, and now handles a number of different devices with wildly different clock frequencies and architectures.

I would rather design the system by taking the maximum execution time into account, and be able to deal with faster execution times. There are other methods of synchronization (external signals, timers, etc) that do not rely on a loop taking exactly the same amount of time every time, as long as a maximum (worst case) execution time is not exceeded.