That would be my vote too. Ideally, I'd like the names to be displayed in the game with macrons, but for the province search to work with or without them: so on the map, you see Tōtōmi, but typing Totomi in the search box will also find it. Remember, the name of modern Japan's capital city is written in English as Tokyo, not Tookyou or whatever...
As for Tootoumi, to a native English-speaker's eyes that looks like the name of a village in Finland, not a Japanese province.
I'm not sure how we will do it yet, but personally I agree with this.