Do the 1st option, too much messing around with list fields in the 2nd option + you said it yourself
Also list fields have race condition issues if two different workflows are adding to a list at the same time. So two notifications coming in at the same time, both adding to the Current User’s list of Messages, you could have issues.
One example: "Add to list" and race conditions
Don’t even bother cleaning up old Messages, let them pile up into the millions then if you notice even a slight lag (doubt it) you can deal with garbage collection later