How would I check that?

RTMT (CallManager->Database Summary), the CLI (utils dbreplication status), or the GUI (Unified Reporting->Unified CM Database Status).  Take your pick!

Any dbreplication status other than '2' is bad...

Here are the results:

SERVER                 ID STATE    STATUS     QUEUE  CONNECTION CHANGED
-----------------------------------------------------------------------
g_pgpublisher_ccm7_1_3_30000_1    2 Active   Connected     140 Aug 17 22:25:09
g_pgsubscriber_ccm7_1_3_30000_1    4 Active   Local           0             

SERVER                 ID STATE    STATUS     QUEUE  CONNECTION CHANGED
-----------------------------------------------------------------------
g_pgpublisher_ccm7_1_3_30000_1    2 Active   Local           0               
g_pgsubscriber_ccm7_1_3_30000_1    4 Active   Connected       0 Aug 17 22:25:09

When I run show perf query class "Number of Replicates Created and State of Replication"

here are the results:

admin:show perf query class "Number of Replicates Created and State of Replication"
==>query class :

- Perf class (Number of Replicates Created and State of Replication) has instances and values:
    ReplicateCount  -> Number of Replicates Created   = 427
    ReplicateCount  -> Replicate_State                = 2

admin:
admin:show perf query class "Number of Replicates Created and State of Replication"
==>query class :

- Perf class (Number of Replicates Created and State of Replication) has instances and values:
    ReplicateCount  -> Number of Replicates Created   = 427
    ReplicateCount  -> Replicate_State                = 2

admin:

Well at least you database appears to be ok.

Just out of curiosity, are you using auto-registration in your cluster?  If you're not using it can you verify that it is off?

How would I verify auto-registration?

All the settings are under the System->CallManager menu.  To enable auto-registration, one has to specify a directory number range for auto-reg'd phones to use, turn on auto-registration and specify an auto-registration CallManager group.  I don't have access to CM at the moment so I apologize for not remembering exactly where all those options are off the top of my head.

Ok, I was able to locate the Auto Registration information.

It is disabled on Subscriber, but enabled on Publisher using extension 7100-7110.  The deleted phones are not using their extensions, they are using their old extensions.

Yes, the extensions are deleted from the unassigned extensions as well!

I know we already checked dbreplication, but...

You stated that you can delete a phone and verify via CCMAdmin that it's gone.  Can you try deleting a phone (and unplugging it before it re-registers) and verifying via CCM Admin on all CCM servers in the cluster that it's gone?  I still feel like something strange may be going on with replication despite the good replication status.  I hope I'm wrong though!

I will give that a try and let you know the results. 

I have also found that a couple phones that were deleted are actually auto registering.  I was able to configure one of the them with a new extension, but when I moved the phone from the Default device pool into one created for the facility, the phone pulled its old extension.  Weird...

Ok, I deleted a phone and confirmed it is deleted in both CCMAdmins.

And if you plug it back in does it come back anyway?