It is determined by the move. For instance, Razor Leaf is always evaded, whereas Tackle always misses. I guess that some attacks (think Earthquake) would sound stupid to 'miss', so they have to be 'evaded'.
I think it does have to do with the move, but it says, "x avoided the attack" when an attack that is intended to hit multiple targets (like in a double battle) misses. For example, in my HG game, it says, "x avoided the attack" when I use Blizzard, which hits both targets in a double battle. Whereas, when an attack like Thunder misses, it just says, "x's attack missed" because Thunder is only meant to hit one target in a double battle. Maybe this is it? I don't know.
And for the record, I'm using Blizzard instead of Ice Beam for the in-game story mode because I'm too lazy to play that Voltorb flip game.