I noticed that after changing our IP, our server shows up last (takes a minute) in the ingame server list, even though no other servers have lower ping for me.

The location you're in or ping you have to the server doesn't seem to matter. Not found any correlation for the port either.  I noticed also some other servers has this problem. Players (including those from the same city the server is hosted in) are complaining not being able to find it and have to connect by console. 

All browser server lists except playrust.io shows it. Ideas?

That's very interesting, but wouldn't that prevent the server from appearing in the list? The server appears, but it takes so long that players think it's not there. 

Oh, I just seen the part where you said players are complaining not being able to find it and have to connect by console and I assumed that's probably why.

If your list is sorted showing servers with random ping numbers, that means you've changed the sorting order (by server name? by players?)

The sorting method doesn't affect how long it takes for the server to be included in the list.

I must have misunderstood. So when you say "shows up last" you're not saying that your server is at the bottom of the list, you're saying that, as you watch the list load, your server doesn't appear immediately, it takes a minute before it shows up, and then it appears normally on the list, in the correct position?

So in other words, you just have impatient players. Why don't you tell them to favourie your server, then they won't have to wait at all.

Also, if you're using playrust.io then bear in mind that seems to cause all kinds of issues, I personally wouldn't touch it with a bargepole for my server.

It would be useful to know what affects the time because it has an impact on server population. If it appears earlier, players are more likely to join. In addition, it's just interesting to know. 

I'm aware of the playrust.io issues.

I have same issue with some host providers.  Exactly same situation and no solution . 
And yes your regular players will join by ip but new ones will not join as they will not wait minute or more for server to appear on list....

IMHO I don't think that's entirely true. When I'm looking for a new server to play on, I wait for the entire list to load before I start searching. People who just jump on the first server they see, they only intend to play for a short time, they are not choosing their long-term server - and I also believe this is a very small minority anyway, most people wait and search because they want a server suited to their play style. So if your server is slow to load I really don't think you are losing any "serious" players.

Even if a method exists to have your server appear before others (which I doubt), I'm sure that anyone who knows it is going to keep it to themselves. I mean think about it. If you have info that gives you an advantage, are you going to share it on a public forum so everyone else and his dog can use the info to get ahead of you?

I disagree with most of it. When I have server loading up instantly on list I do have 350/400 new players visiting server per day. When I had dedicsted server which had ping 4ms higher in my case it wasn't loading instantly. Number of visitors on server dropped to 50-60 per day including regulars. I hardly saw new players. Past fewmonths I tested most popular hosts and spend fortune on them. Some of them refunded money, some not. But when we came to issue related to server displaying on list they could not improve it. Most the time answer was: its isuue with face punch- which from my experience I know its not true. I still do not know what factors dicide about server displaying ir not on list and how long it takes.
In my game servers with ping higher then 19ms dont display at all so I would never see them.
Regarding ads- I never found any website or streamers... where I could advertise servers for money. I advertised them in few places and never really had anybody joining from adverts. From my experience advertising is just waste of time.

Encourage your players to learn how to add your servers to their Steam Favorties and they should Never have to "search" for a server again.

1. In Steam up top click View/Servers then click Favorites Tab
2.On the servers Favorites tab click Add A Server button on bottom Right
3.Paste the Ip/Port above and hit Enter. 
4.Open Rust and under Favorites now on server list will be this server you just added.

There is several other ways to bypass them seaching for servers as well.
Be creatve, out think the issue, it's not a big deal, encourage a better way of finding the information they need a more reliable way.