Let me stress this...IN YOUR OPINION, these characters are deconfirmed. No one is every truly deconfirmed until Ultimate is done and they aren't in, so this is simply your own mindset.
In reality, Spring Man was heavily considered as the playable character for ARMS by Sakurai before ending on Min Min due to her popularity and the creator's request. Never forget that Spring Man is already a Spirit, Costume and AT from the base game. This means that ATs are not an automatic denial of a characters chances, which means Waluigi could flat out just happen due to fan backlash and demand. The real issue for Waluigi is what other content he could come with. Waluigi already has music tied to him in the base game as well as Mario Sports content in stages and music already in the base game, so what would they be able to bring to the table for him? I'm sure they could think of something, but this is clearly the real hurdle for Waluigi: what content does he bring?
I've been over this way too much in recent days, but returning Mii Costumes don't deconfirm either. Saying a Mii Costume 100% deconfirms a character is simply moving the Spirits Deconfirm goalpost: it's literally the same argument, but for slightly different content. Deluxe Costumes are the only ones to really fret about, and even they aren't fully written off, because as long as the DLC goes on things can change. Thereby Geno isn't deconfirmed and is an extremely viable option for a Mario character.
Paper Mario isn't truly deconfirmed either, and he is a very good choice as well. In addition to you mentioning King Boo, we've got Fawful, Toad/Toadette/Captain Toad, Wart and the possibility of what you mentioned with another generic Mario enemy. Funnily enough, the list of fan requested Mario characters is very small, but the list to pick from is larger than it probably should be.