How do I validate that my purge hasn't deleted the wrong data?
Declaring foreign keys would be a great start, but I think you know that. While they will ensure what is in the database is consistent they will not ensure it is correct. In other words they can't stop you deleting something that should be kept. For that you need to program the "should be kept" rule somewhere. You've put the "should be removed" rule in stored procedures. I think putting the "should be kept" rule in triggers will give an additional level of assurance.

In past purges we have implemented extensive reconciliation scripts. Counting the rows is a good start. Summing values by multiple combinations of keys is better. SQL Server's GROUPING SET syntax makes this not much less efficient than a simple count. Perform these aggregates before the purge with only the retained rows in the WHERE clause. Preform them again afterwards with no WHERE clause. If too many or too few rows were removed the before and after numbers will be different. Because you summed by lots of different keys it will be easier to identify the offending source rows.

Given we accept an error can occur, it is possible that error will delete some number of rows it shouldn't and leave the same number of rows it should. Unlikely, but possible. By summing the error has to remove / leave exactly balancing rows. This is even less likely. By summing over multiple keys the chances are further reduced. This can be continued until an arbitrary level of assurance is achieved.

I would not suggest deploying this against production, at least not initially. A copy will suffice to perform the cross-checks, and to validate the validation code. If you can confirm here that the deleting procs are working as intended you have confidence to deploy them in production without the extra checks.