Visual Studio: Where does it store "Set as startup project"?

Yes, it gets stored in the .SUO.

Although this can be an issue if you're often checking out branches or deleting your trunk workspace and checking it out again, it only takes a second to set it, so hopefully it's not too big an issue. You should definitely keep the .suo files out of the repository if you can.

Yes, it is stored in the .suo file.

Here's a similar post explaining why.

As @Gishu and @misteraidan both said, Visual Studio uses the first project listed in the .sln file as the default startup project. If you have a primary project that should always be the default, just modify the solution in a text editor to list that project first in the list.

EDIT

Yes, it still works in Visual Studio 2019. By default, Visual Studio uses the first project listed in the solution file (.sln) as the default startup project. However, if you manually change the startup project inside Visual Studio, that setting appears to be stored in the .suo file located in the hidden .vs folder, and it overrides the sorted order in the .sln file.

However, if you close Visual Studio, delete the .vs folder, and then re-open the solution, whatever project is listed first in the .sln file regardless of project type will be used as the default startup project.