MySql : how can I implement a sort of "read/not read yet" topics?

Your suggestion sounds good. I would make user-field also a foreign key - it gives you a bit more flexibility.

Are you sure all 9000 topics are read by all 9000 users? I mean is this reality? Like you said, topic-entries are deleted when new message is added. And when that happens, another 9000 entries are deleted :)

I would index the table and go with your suggestion (with user_id change). If the table size gets in your way, you can always change the implementation later. Most likely it will never be the issue anyway.

May I suggest a different approach?

Make use of web browser history mechanism.

Every topic can get a new, unique URL every time a new message is added there. It could include the number of messages, last modified time or a combination of both.

If the user did see the topic, he must have visited it, so a properly set up CSS can help identifying the read ones. You can even use some client-side scripts to modify the behaviour of the page based on that.

Another way to do that would be to keep the watched topics table the way you want to do it, but also store last visit time in user's profile and show all topics as read that haven't changed since that time.

However it's pretty safe to assume that all users reading all topics is very unlikely.

For the deletion: you could save what the latest msg-ID was the user saw. This way you do not have to perform a lot of delete actions every time a msg is posted in a much-viewed topic.