From the review you linked:
So they seem to think it does require power and consider a 4 ohm capable amp required. Certainly the 4250 is no wimp and can generally handle 4 ohms, but at the same time, it does have it's limits and you are trying to fill a larger space.
Looking at the frequency response there is quite a dominant hump in the bass between 50Hz - 200Hz. This has a good chance of making things boomy or muddy in any room.
If you are not using Audyssey, you should because it will help to tame this hump and any room effects associated with it!
Give Highfigh your room height and let him calculate your room modes.
This is how I would address this:
First - Audyssey; you paid for it. It is free and it is often pretty good at addressing what I guess to be your problem.
Second - Bi-amp if you like since it is free. There is some chance that for your AVR and your speakers it may help, just don't bet on it!
Third - After you find out about room modes for your dimensions; consider what high-figh is saying about altering your room dimensions. Depending your personal willingness to have walls set up determines whether this is really 3 or not, but 1 & 2 were essentially free, so they come first!
Fourth - Subwoofer; Find one that will work well up to 250Hz. You may not need to go that high, but with the hump in your bass, I would hedge my bets by being able to off-load the full hump frequencies to the sub. You are doing two things here - removing the hump frequencies from the speakers, and off-loading the low frequencies from your AVR (which has the same effect as getting a more powerful AVR).
Fifth - Amp. I place this as the last option because the rule of thumb is you should double your power to get an appreciable difference, Essentially, you are looking at 300WPC. That is the cost of a good sub, but I think a good sub will do more to help your problem.
PS - you really have not attempted to better describe what you mean by "sounds messy". Read a bit here on the sound of clipping. If this is what you are hearing, you can probably forget everything I said and get more power.
http://www.avsforum.com/forum/89-speakers/1399048-what-does-clipping-sound-like.html