Purging of unreferenced data via unconditional DELETE, by leaning on foreign key constraints
One option would be to create views for these "inconvenient" tables that only return rows where all foreign key relationships have been broken.  Then you could do unconditional deletes from those views.

You would have the overhead of coding each of these views*, but that's a one-time startup cost.  This is essentially the same as what you mentioned already:


  I could write some code find out which rows in a certain table aren't referenced anywhere else


But in the end, you will have the "unconditional deletes" in your cleanup job.



Note: the approach below would not scale well on really large tables without indexes, and potentially some form of batching (e.g., putting a TOP 100 and ORDER BY in the view definition

Say you have two "main tables" that reference this "inconvenient table" (the one you need to remove rows from when they are no longer referenced:

CREATE TABLE dbo.InconvenientTable
(
    Id int IDENTITY(1,1) NOT NULL,
    [Description] varchar(10) NOT NULL,

    CONSTRAINT PK_InconvenientTable 
        PRIMARY KEY (Id)
);
GO

CREATE TABLE dbo.MainTable1
(
    Id int IDENTITY(1,1) NOT NULL,
    [Description] varchar(10) NOT NULL,
    InconvenientTableId int NOT NULL,

    CONSTRAINT FK_MainTable1_InconvenientTable 
        FOREIGN KEY (InconvenientTableId)
        REFERENCES dbo.InconvenientTable (Id)
);

CREATE TABLE dbo.MainTable2
(
    Id int IDENTITY(1,1) NOT NULL,
    [Description] varchar(10) NOT NULL,
    InconvenientTableId int NOT NULL,

    CONSTRAINT FK_MainTable2_InconvenientTable 
        FOREIGN KEY (InconvenientTableId)
        REFERENCES dbo.InconvenientTable (Id)
);


The inconvenient table has 3 rows, all 3 of which are referenced in MainTable1, while only 1 is referenced in MainTable2.

INSERT INTO dbo.InconvenientTable
    ([Description])
VALUES
    ('One'),
    ('Two'),
    ('Three');
GO

INSERT INTO dbo.MainTable1
    ([Description], InconvenientTableId)
VALUES
    ('One', 1),
    ('Two', 2),
    ('Three', 3);

INSERT INTO dbo.MainTable2
    ([Description], InconvenientTableId)
VALUES
    ('Two', 2);


Now we need a view that shows all rows in dbo.InconvenientTable that are not referenced by the two main tables:

CREATE VIEW dbo.InconvenientTable_RowsToDelete
AS
SELECT it.*
FROM dbo.InconvenientTable it
WHERE 
    NOT EXISTS (SELECT NULL FROM dbo.MainTable1 mt1 WHERE mt1.InconvenientTableId = it.Id)
    AND NOT EXISTS (SELECT NULL FROM dbo.MainTable2 mt2 WHERE mt2.InconvenientTableId = it.Id);
GO


Currently all rows are referenced, so this query returns 0 rows:



Now let's delete the 'Two' row from both main tables:

DELETE dbo.MainTable2 WHERE InconvenientTableId = 2;
DELETE dbo.MainTable1 WHERE InconvenientTableId = 2;


And now the view returns that unreferenced row:



Now we can delete everything from the view, which successfully removes the 'Two' row from our inconvenient table for compliance reasons:



*You could also attempt to automate the creation of the views with dynamic SQL and metadata queries, but that seems risky