I need to retract my previous "solution" as we found out that deleting the invalid certificate was not the actual fix. About a week after I posted the solution, profiling stopped working. I assumed we were hitting a bug but CP was actually working as designed. Weird, eh? I'll keep it short, but here is ultimately what I learned:
In a CP cluster, when all CP servers have profiling enabled, only one of the servers can be the master profiler just like you can only have one publisher. The master profiler is selected via election, and the server with the lowest UUID wins. Although all CP servers may have profiling enabled, only the master profiler can profile devices. Having an election for the master profiler provides a level of redundancy should something happen to the CP server acting as master profiler.
For non-profiling redundancy, enable profiling on only one CP server and point all DHCPs relays to that CP server.
For profiling redundancy, enable profiling on X amount of CP servers, and setup DHCP relays to those CP servers.
This is what the CP engineers suggested to me after having profiling dificulties for about a month. I was surprised to find out that of all the people I talked to, no one (colleagues, SEs, TAC) was aware that this is how profiling works in a cluster. I couldn't find any mention of this in the CP documentation, so I requested that it be added. Hopefully, it's added so that others don't have the same issue and bang their heads against the wall like I did for a month.