Regulus's prime weakness is that each of his skills take several points before they can become a severe threat; coupled with him having several "must-have" passives, this usually means Regs don't have a "build" of several abilities--they usually have to choose one ability to put many points in, and neglect the others. As a result, they are something of a one-trick pony: where any other Demigod can fall back on their other skills if one is ineffective, Reg is pretty much %&$@ out of luck if you can get around his one strong skill.
As general advice, all of Reg's abilities work best when he is alone or unbothered; therefore, don't give him a moment's rest. Force him to be dealing with SOMEbody, every minute of the game, and you will exhaust him and overwhelm him. Don't worry too much about him pestering you from just out of range--remember, you aren't taking the lane to kill Demigods, you're taking the lane so you can kill creeps for xp and gold, and let your creeps reach the towers. Always threaten Reg until he retreats to a tower, then back up and kill creeps.
By constantly threatening Reg but focusing on the creeps, you will inevitably win; even if he does get a lot of damage on you, as long as he doesn't kill you, you will have gained a lot of strength on him--he's wasted too much time attacking you, while you've been building up xp and gold. A Reg denied creeps will have to rely entirely on Demigod kills for strength, so just make sure you never, ever die to him--teleport, heal, or even go get killed by a tower, just so he can't get the full benefits of killing you.
As for other ways of stopping him, flag locks stop him from getting xp by capturing, denying him even further--this can be devastating early game, when he desperately needs skill points to get even one viable skill. Always control the xp flag, just so he has to work even harder to overcome your lead. Priests will keep you healed while you fight, making it that much harder for him to pester you into fleeing; healing in general shuts him down quite quickly, since he's essentially all spike damage--he's relying on the first two hits deciding the fight. Stacking speed is particularly important against Reg--you had better believe that he's going to be, so you have to be sure he can't flee guaranteed.
The best way to shut down Reg early is kill the tower closest to the lane, so he can't attack you while you're killing creeps--this will force him to retreat much further, or move to a different lane. If you've taken down the towers on all the creep lanes, you've pretty much shut him down for good.
Remember, keep HIM responding to YOU--this will keep you ahead in xp and gold, and deny him his critical advantage of initiative; I always say Regulus is like Batman--even though he isn't as strong as anybody else, he has the right tools to win any fight, if he has time to prepare. Therefore, don't give him time to prepare.
As for countering his skills:
If his strong skill is Snipe, simply carry a minor combat potion around; it will take a tremendous amount of effort and shenanigans for a Snipe to kill you through 750 health. As soon as you suspect he is preparing a snipe (i.e., you are fleeing and a Snipe would be lethal,) pop the potion and you will almost certainly survive--also leaving the Reg puzzled as to why a sack of cash and xp didn't just appear in his lap. If this Reg also uses Heaven's Wrath, it might be a bit tougher--consider buying one of the powerful combat potions from the artifact shop, or just flee earlier.
If his strong ability is Wings, he will be very effective at killing creeps, and even more effective at pestering Demigods, but he won't have any good tricks, except maybe a really weak Snipe. It will be vital not to let him control a lane, and important to have good combat tricks--since he basically can't do anything but autoattack, any skills you can use to give yourself an advantage in combat will shut him down quickly. Remember, now his only recourse if he's losing is to run, so snares/stuns/etc will be even more valuable.
If his strong ability is Mark... that would be really weird. I guess once you're marked, try and get it off of you quickly, so you don't have the speed debuff when you're trying to chase him.
If his strong ability is Mines, this will be a hard fight, as mines are really good against both creeps and Demigods. First and foremost, mines can be interrupted with a quick trigger finger--TB's Deep Freeze is particularly nasty for this, since it's at-range, and increases Mines' already substantial recast time. Generals have a big advantage against mines, as they can just send their minions forward to set them off; with Horn of Battle, they won't even flinch.
If you're not a general, think carefully when approaching him: "where would he most likely throw mines to block me?" Try to approach from an unexpected direction. If he tries throwing mines at you in combat, run towards him as fast as you can--with any luck, he'll whiff the mines, and you'll now be standing behind him--directly between him and escape, and with no mines for him to hide behind. This is difficult to pull off, but devastating if you do--if you have any stuns or snares, he might just die outright.
If he throws mines anywhere else, pay careful attention, and assume he's about to try and lead you over them--do not follow. Granted, it can be very difficult to dodge mines in the thick of combat, they tend to explode just a tad too quickly, but it is still possible.
A great way to circumvent mine-dodging is to watch him from outside range until he throws mines to kill a wave of creeps; the second these detonate, rush him down, since he now has to wait through the mine's significant recharge time to throw them again, and with any luck he'll be on the run by the time they're ready. In all cases, stack HP like a mofo, just so that getting pegged with all three mines doesn't instantly give him the upper hand.
I agree with you that Reg is the most frustrating DG to play against, due to the impersonal, indirect, pestering manner in which he fights, but by paying careful attention and focusing on the right target, he can be beaten. Good luck!
