Review of Log Messages Database Schema
First, I love that you have isolated your actual messages into it's own table, that was going to be my first suggestion but you had already gotten there.
Otherwise, I think your first design is good.  By keeping the message log itself (the meta data) isolated from the message body you will (with proper indexes) be able to find messages very quickly.
My only word of advice for you would be to do the delete check as part of the transaction that is writing the message (and to make that a small number).  This will make the cleanup action part of the message writing logic and keep things moving along quickly.
Something like:
Delete TOP (100) old messages that satisfy criteria
Insert new message