I guess this isn't really much of a Perl question at this point, maybe you would have better luck with a database design forum. With that said, not knowing much about how you decided to set up the tables, perhaps what you want is a seperate status table:

CREATE TABLE status(
  user_id INT        NOT NULL PRIMARY KEY,
  msg_id  INT        NOT NULL,
  status  VARCHAR(3) NOT NULL
)
[download]

That way you could query the status table per user for messages that aren't deleted. Hope that helps.