@Jubilation: Yes it seems to me like you are perhaps under level to be challenging Wallace because in my Sapphire version my I believe level 51 Pikachu took Milotic out like nobody's business. Or my Vileplume might have done it, I can't remember it was a while ago but I remember it was not a challenge because I made sure to be high leveled after that damn milotic was such a pain in the butt to me in my very first Third gen, Ruby file. So perhaps try a grass pokemon as opposed to electric and definitely try to out level it by at least five.
Also make sure you are not using a lower level move such as Thundershock as opposed to Thunderbolt or Thunderbolt when you could use Thunder.
Another thing to consider is an Alteria with Perish Song. My bestie told me that it really saved her ass against Steven in her Ruby. So although I have yet to use it myself(although I will I am training one in my Ruby now) It sounds super useful.