This question is not easy if not nigh impossible to answer exhaustively, for a number of reasons. Since my previous answer cited a few misleading facts and in retrospect lacked proper structure, I decided to revise and more importantly, restructure it. So lets look at a few points.
1. What is maximum warp?
The term maximum warp is somewhat loosely defined. Check this Memory Alpha page on Maximum Warp for more details.
Most of the time it's apparently used to describe the maximum warp speed that could be safely maintained for a prolonged but limited period of time. Usually a few hours, maybe a day. There is also cruise speed which is lower (say Warp 6 for example) but can be maintained for several days without issue.
There are examples cited on the Memory Alpha page where ships supposedly traveling at maximum warp accelerated even further. So if the order "Go to maximum warp" is given, it usually means accelerate to the safest maximum.
But the engines can be pushed further but either only for a much shorter time or by risking serious damage.
To provide a real life analogy: If you want to drive fast for a prolonged time you don't rev your engine up into the red zone but stay just shy of it, where it's much safer to operate the engine. If on the other hand you need that extra 5 or 10 miles per hour to overtake, you push into the red zone but only as long as you have to.
Maximum warp, the actual maximum achievable speed and the time period these can be maintained vary from class to class or even ship to ship if they have been modified. Which brings us to the next paragraph.
2. Not every ship is like any other and the same is true for their warp drives
Each ship in Starfleet is designed with different purposes, roles and requirements in mind. The Sovereign-class for example was much more focused on combat than previous Starfleet designs, featuring a greater number of weapon systems, better shields and so forth. This also means that it had much greater power requirements then other ships and the warp core is also the power source.
No matter how advanced your warp drives are, there is no such thing as 'one size fits all'. This is why you can't just take a warp drive designed for the Intrepid-class (for example) and put it in a Sovereign-class ship. Creating and maintaining a warp bubble is a masterpiece of engineering and requires to balance the warp drive against the other characteristics of the ships. This is why even with an essentially identical warp drive the outcome can be different.
Other systems on the ship might produce limiting side-effects that keep it from achieving the same results that other ships got out of it. Take the D'deridex warbird for example. It had some major problems because it used a singularity as a power source which was hard to control at high warp speeds. Because of this it could reach the same speed as the Galaxy-class ships but it could not do that safely. This was a pitfall of the used technology however and had nothing to do with an inferior warp-drive.
3. Different sources give different speed or none at all
If you consult various sources for technical specs you will probably get as many answers. The Enterprise-E is apparently never said on screen to do more than Warp 8. At the same time they don't state what maximum warp is for the ship. According to other sources it's apparently around 9.995.
At the same time maximum warp of the Intrepid-class is 9.975. The Intrepid-class was stated in Star Trek: Voyager to be the fastest in the fleet. Later the Prometheus-class was stated to be even faster at Warp 9.99. However this might have been only true at the time the USS Voyager and USS Prometheus launched respectively, since ships were also retrofitted to make use of further advancements in warp-drive and technology in general.
This might have lead to ships ultimately being faster than they were originally capable of. Otherwise the stated maximum warp of the Enterprise-E would contradict the statements about Intrepid-class and Prometheus-class ships being the fastest in the fleet.
The Scimitar on the other hand was stated to be at least capable of Warp 9.7. But his doesn't tell us how fast it could really go or for how long.
At this point I would also like to point out, that the Scimitar was a unique ship. From the get-go designed to be a superior war ship, with superior shields, cloaking and a lot of firepower. Throwing in a powerful warp-drive is only natural. It probably also did not have the same restrictions as Ship-of-the-Line designs like the Sovereign-class or D'deridex which were essentially designed for mass (I use the term loosely here) production. The goal for them was not do build the most powerful ship, but a powerful ship that could be produced in bigger numbers.
4. Movies and TV show do not provide a realistic time scale
We don't really know how long the chase lasted because in movies or TV they don't give you a timescale most of the time. Stuff just happens and you feel like it takes maybe a day for everything to unfold while it actually is supposed to be taking a week.
I couldn't find any reliable information on how far away Romulus is from Earth but given that it's in the Beta Quadrant while Earth is in the Alpha Quadrant I would guess that it takes more than 12 hours even on high warp. We established that ships can maintain their maximum warp only for a limited amount of time so the Enterprise probably could not do the entire trip at Warp 9.995.
5. Overtaking something is not necessarily about top-speed and power
No matter how far away Romulus is from Earth, I think we can all agree that were talking long distance here. In you question you assume that the Scimitar must be faster than the Enterprise-E, because they catch them. It's understandable to think that way because that's how it works most of the time in real life. If you want to pass someone on foot you just go faster. We naturally assume that a powerful car can overtake a slower car by just going much faster. However in the long run average speed is actually more important.
If you're in a marathon and pass someone and then you slow down because you're out of energy, that someone can pass you again and be at the goal before you if they were able to maintain a steady pace. The same happens with cars on the highway and with ships in space. The Scimitar didn't have to be faster than the Enterprise-E. It just had to maintain a higher average. Even if the Enterprise dashed ahead at a higher warp speed, unless they could keep that up long enough to bridge a significant portion of the total distance, the Scimitar could eventually catch up by maintaining a higher average speed. But since we don't exactly know the average speeds of both ships this will remain a hypothetical assumption.
6. Captain Picard would not push the Enterprise
In one of your comments you wrote that the Enterprise would go at maximum warp to reach the fleet as fast as possible. This is only partially true however. If we're talking maximum safe warp, than yes, that's probably what Picard would do. But he would not push the ship beyond reasonable limits. Why? Because he was going into a very dangerous fight with a superior enemy. Going into such a fight is a bad thing. Going into such a fight with a damaged warp core, propulsion system, or otherwise damaged system is nigh suicidal. That is if your ship is not ripped apart or blown to pieces by your warp core. Picard would not risk this. He would run as fast as possible but not beyond reasonable limits and risk getting caught 'pants down'.
7. Romulans have advanced technology and an effective intelligence service
Romulans are one of the major powers in the Alpha and Beta quadrant, although they apparently use some subterfuge to look more powerful than they actually are. They are, however, one of the more advanced races and have also been around for while and had some time to develop their technology.
In some cases they are more advanced than the Federation, although I always got the feeling that they are constantly losing ground technology-wise.
They are also know for their intelligence service which even managed to hijack the Prometheus-class prototype. So even if they started to fall behind they were certainly capable of stealing technology or parts thereof.
Based on these points I don't see how to give an exhaustive in-universe answer. There is no reason to believe that Shinzon was incapable of building a ship that could catch the Enterprise on it's way to Earth. We also don't know for sure that the Scimitar is actually capable of doing so. There are just to many unknowns and missing facts about the entire event.
Which is why I will stay with my initial conclusion:
The Scimitar could catch the Enterprise, because the writers wanted it to be that way.