I tried it earlier and the first time I spoke to him afterwards he said it again. So unless there's a delay I guess it's not going to work. Is there a decent chance he'll ask about changing it again soon, if I talk to him several times a day?
Maybe try to wait another day? I don't know how long it takes to become effective.
Which part did you change, and was it changed by you or by someone who had the villager before?
In my experience, yes, you do get a chance to change it again. It can take a while, though, even when you're talking to them regularly, so don't despair. In my experience it's a bit hit-or-miss.
Is it something offensive or is it just a typo or something? If it's something you can ignore, then I wouldn't go out of my way to talk to them a lot. I'd talk to them regularly but since it can be a bit random, don't feel pressured to talk to them several times a day unless you want to.
Another way they change those is by pinging you, so you can always do the pinging trick once you have the wetsuit. Just swim out into the sea and stay there for five minutes or more. When you go back to the shore, make sure that villager is the first one you see. You can trap them or walk in front of them repeatedly. When they ping you it can be about anything (PWPs, moving if they're due to move, trades) but some of them will be about this. If you empty your pockets so they won't try to sell or trade with you, that can also save some time but it's not strictly necessary for it to work.
Finally, sometimes they also change greetings and catchphrases at random by getting them from the other villagers, so there's always a chance that your villager will just do that and save you some work.
Quick question: If you went to Nook's Homes and selected a mailbox for example, can you go to another town and choose another one? Or is it only once choice per day?
I don't know if it's possible or not but I don't think so. If it is, I think you'll still lose the money you paid for the first mailbox and it will be overwritten by the new one.