Is it that by original design, they were simply omitted?
In general no, it's largely because if nobody complains then there's no incentive for somewhere to spend the money/effort to replace a missing seat. In some places you do get purpose made toilets that don't have seats or don't have removable seats however these are obvious and the cases you mention it's likely just poor upkeep but the seats where there originally.
And, yes, people may steal them for whatever reason making them less likely to be replaced.
How can I have better luck finding a toilet that actually has a seat? (Or an accommodation where the toilets will likely have seats?)
Look for places where people would expect seats and complain if they're not there. I.e. higher-end hotels and restaurants, anywhere likely to be populated by tourists or locals with money that will complain about it.
I'd expect seats in any en-suite toilet in a hotel (possibly not in any public toilets they have) unless it's a really cheap place or a remote place that possibly never had them. It sounds like you're implying you're staying somewhere where this is not the case.
Also any public toilet that charges a fee is more likely (but definitely not guaranteed) to be in a better state of repair.