I have a found a paper that suggests that the development of participles to prepositions is somehow a "gradual" process of grammaticalization: "Prepositionalities of Deverbal Prepositions:
Differences in Degree of Grammaticalization", by Tomoaki Hayashi, Papers in Linguistic Science, No. 21 (2015), pp. 129-151. It discusses many words, so it doesn't have much in-depth discussion of starting, but it does mention starting and provides some data that is supposed to indicate that it has progressed substantially along this path.
I'm not completely convinced by the data (or by the theoretical claim that the participle/preposition distinction is gradual rather than discrete), but I think that this paper is relevant to your question and brings up some useful candidates for verb vs. preposition tests. To me, a test involving cleft constructions seemed like the most convincing piece of evidence* to support classifying "starting" as a preposition in sentences like the one in your post.
*Aside from the argument that you already mentioned about "starting" not having "people" as its implied subject. Hayashi brings that up early on in the paper, citing a sentence from Hopper (1991: 31), who uses this as an argument for considering considering to be a preposition in the following sentence: "(4) Considering its narrow beam, the boat is remarkably sea-worthy" (Hayashi p. 131).
Cleft constructions seem to indicate that "starting" can head a PP
In section 3.1, Hiyashi says that cleft constructions can be used to distinguish PPs from verb, adjective and adverb phrases. Supposedly, PPs can be emphasized in cleft sentences, but VPs, APs and AdvPs cannot. Hiyashi gives the following as examples of unacceptable sentences, citing Emonds 1976: 133:
(16) a. *It was too carefully that she spoke. (AdvP)
b. *It’s very unhappy that Bill is. (AP)
c. *It is blow up some buildings that you should. (VP)
Hiyashi used the following sentence to test the acceptability of starting in a cleft structure:
(B34) It will be starting today that Miss Carey will be in charge of the Sales Department.
(Appendix)
In Table 2, Hiyashi categorizes starting as having a "prepositionality" score of 3.5 (where the maximum would be 5.0). This number was derived by averaging
the acceptability scores given by "eight English native speakers: four American English speakers, two Australian English speakers, one British English speaker, and one Canadian English speaker" (p. 138).
I do personally find these two examples fairly acceptable (if I were to score them out of 5, I might give them somewhere around a 4). I found similar examples from a Google search of the sequence "it’s starting today that":
Their first album will come out at the end of the year, but it’s starting today that you can expect to be completely gobsmacked.
(DERBY MOTORETA’S BURRITO KACHIMBA (ES), Primavera Club website)
They set up two new counters by the Broadway entrance to deal customers today, as you know it's starting today that customers may buy their fragrance with the passes to meet Mariah, fans started to wait in line in the afternoon and camped outside to be sure they can buy their package.
("Macy's last night", October 2007 - Heroes of Mariah)
My main concern with this test is that I'm not sure that it's actually completely unacceptable to use a verbal participle in a cleft construction like this.
"Starting" seems to be modified more freely by adverbs as a verb than as a preposition
In section 2.3, Hiyashi says that one possible criterion for distinguishing verbs from prepositions is the acceptability of adverbs with the word (citing Hayashi 2014). Hiyashi says "when a verb becomes grammaticalized into a deverbal preposition, it tends to become less acceptable in collocation with adverbs" (p. 134). Hiyashi's 2014 informant (a native speaker of of British English) judged it unacceptable to modify starting with the adverb "typically" in contexts where it could be analyzed as a preposition (Table 1 and (14), p. 136).
I'm not sure about this judgement or its relevance to the question of starting's part of speech. "Typically" doesn't work in your sentence ("((*Typically) Starting in March, people will also finally be able to buy the Exodus phone with cash and not just cryptocurrency") but I think that it would be excluded for semantic reasons even if "starting" were a verb: you wouldn't use "typically" with a verb that is talking about a specific one-time event. Another adverb that I've seen mentioned in other sources as a likely modifier of verbs is "carefully", but again, the semantics don't seem very compatible with "starting". I feel like it would be difficult to get conclusive results with tests based on -ly adverbs.
"Right"
I think it's well known that being able to be modified by "right" is a characteristic feature of prepositions.
"Right starting" sounds completely wrong to me, so when I first read your question, I didn't think that this test could be used to show that "starting" has characteristics of a preposition. However, Hiyashi reports an average acceptability score of 2.5 (out of 5.0) for starting preceded by right in the following sentence (Table 3, p. 140).
(C34) Right starting today Miss Carey will be in charge of the Sales Department.
(Appendix)
I'm less than completely convinced by this data (even if some speakers will acccept this, I still find it a bit hard to believe that a native English speaker would ever produce "right starting"), but it's evidence nevertheless.
It seems that some deverbal prepositions do not take ordinary NPs as complements
Like TaliesinMerlin, I thought that the complementation pattern of starting seemed unsual for a preposition. It takes a PP, or an NP that distributes like a PP (e.g. "starting yesterday"), but it doesn't seem like it can take any regular NP as a complement ("starting *(from) my admission to the school").
However, Araucaria pointed out in a comment that similar patterns of complementation exist for other words that CGEL classifies as prepositions. And Fukuda (2017) "On the Historical Development of During" mentions some similar deverbal prepositions: according (to), owing (to) and pertaining (to) (p. 124, (5)).
"New members of ‘closed classes’ in English", by Brett Reynolds and Geoffrey K. Pullum (2014?), includes starting in a list of words that "might reasonably" be categorized as de-participial prepositions (§3.1), and makes the following note on what it can take as a complement:
- Prepositions beginning and starting typically take an in-phrase complement, but there are also examples with a with phrase. In fact, a variety of temporal expressions should be possible complements: several years ago, last year, only quite recently, and so on