I experienced the exact same thing in a game I played QoT (me) v. Regulus.
I dominated early, controlling the entire middle, outleveling him quickly. However, he eventually surpased me in levels, despite my constant harrassment. I did end up winning (got giants, we were both 20, I controlled artifact hut enough to prevent him from getting them and keep me supplied) though not nearly as quickly as I should have.
Here is what I learned from that game:
1) Ranged Assassins (TB/Regulus) seem uniquely able to make impressive comebacks. In DOTA (*gasp*, a DOTA reference, shun me!) we call this a "late game hero". These heros can be effective early with mines and ice centric builds, but they both are almost guaranteed to get huge later. How you counter this:
2) Press the advantage early. General v. Assassin, in most cases, generals need to be shutting the game down quickly. You will be more powerful early and you have to use this to start pushing down towers. Its easy enough to tank a tower with most generals at level 5-7. After your kill, you should have immediately started in on his defenses. Furthermore, attacking towers will force him to come to their defense, which prevents him from farming or recapping your flags and grants you more encounters.
3) Choose the important flags. You dont need to own all flags at all times. Choose the ones you need and cap those. I like to hang on to the +20% experience flags, creep hp buff flags, regen flags (Mana>hp usually), and celerity flags, in that order of importance. Usually, choosing 2 or 3 of high importance that you can continually control and farming creeps nearby is more effective that running around the map getting them all. (Disregard all this if you are playing Dominate mode).
4) It sounds like you upgraded your creeps (added priests) and he didnt. Priests give the other team experience and gold, a lot more than normal creeps. If he hung out between his towers all game, farming your creeps and you werent there to take advantage of your bonus firepower, he would have gained more than you did from them. As a general rule, once you buy priests, you are committed to using them to push down towers. With oak wards/shields/bishops/seige-dems and priests, its easy to push down a tower if not an entire base even with an even level regulus wailing on you. Rinse/repeat that. You dont buy potions and not use them when you need to, creep upgrades should be the same way.
5) Assassin players often buy the experience upgrade. This could account for part of his leveling speed, he spent his money on himself rather than his base (which is a good choice for Regulus) or any turtling style. The only counter to this is to make sure you are getting your money's worth on your upgrades (see 4).
6) Maintain your advantage. 1 (anyone) v 1 Regulus can be tough, especially on small maps where his range and mines allow easy control of choke points. However, your match-up was, in some regard, favorable to you, it just required a lot more skill. Basically, you have to keep up the pressure (alertness) all game, because any mistake at that point will help him a great deal. He is lucky in that he needs do nothing but wait for you to make a mistake. Regardless of what most people tell you, its fairly simple to throw mines and right click people when you have a range/dps advantage over your opponent. To use a DOTA parallel that will get me hated (but hopefully help some people understand), regulus is OFTEN BUT NOT ALWAYS played like the Dwarven Sniper from DOTA. Sniper is often considered the worst Dota character because he is fragile and item dependent. However, a built sniper (all the best items) is probably some of the most effective DPS in the game. Defeating Sniper is (in DOTA its simpler) a matter of suppressing him early and knowing how to prevent him from getting huge.
Disclaimer to all: I am NOT saying that Regulus sucks or that Regulus players are noobs. I am however saying that he is more straight forward to play than some. His skills are less complex and DPS abilities are always easier to time than disables or debuffs. I have no doubt that there is stratification of skill levels for straight forward characters and that, the more you know, the less straight forward they become. I will however maintain that regulus and other DPS characters like a fire TB is easier to pickup and be successful with than other characters. If you dont believe me, try an experiment, assuming you havent before, go try playing Regulus in the single player, nightmare level tournament. Now try the same with Sedna/QoT/or Oak. Compare results.
