I don't know enough about Kim, since I'm only 5 or 6 episodes into VOY, but I think part of the problem with Mayweather was the actor. I used to think that Montgomery just wasn't very good - but I don't think that's the case anymore. I saw his indy movie I'm Through With White Girls, and really, he's very funny and not stiff at all. I'm reminded of a commentary on the DVD I think for Similitude. Coto (again, I think) talks about how difficult it is to write dialogue for Trek because it's formal and not very colloquial at all. Even though ENT wasn't as stagey as, say, TNG, it still had a very formal cadence to it. It didn't fit Montgomery's Gen Y style.
So I think there's some truth to the idea that the actor turned out not to be a good fit for Trek, and so he was used less and less (because writing a comfortable style for him wouldn't fit with the series). You do get some flashes of naturalness, like off-duty scenes in the Mess ("You'd like [the movie], Malcolm; things blow up") and his wonderful "sweet spot" scene in Horizon.
As a character, though, it's clear that he was wildly talented as a pilot, so I don't think Mayweather was useless.