Complex key constraint: allow only if uuid is new or another column matches
This is a normalisation issue as timestamp is functionally dependent on non_unique_id.

So there should be another table with primary key non_unique_id and the corresponding timestamp.

In SQL Server/Azure SQL Database you can enforce this with an indexed view though.

Create a view with schema binding and definition

SELECT non_unique_id,
       timestamp,
       COUNT_BIG(non_unique_id) AS Count
FROM   dbo.YourTable
GROUP  BY non_unique_id,
          timestamp 


and then put a unique clustered index on column non_unique_id in the view.