Did you say you tried distance / time and had problems?
Have you ever looked at RoboCode? It's an IBM sponsored game environment. You write autonomous robots and send them into battle. I bring it up because there are links to source for user-designed robots. Some are very elaborate - thousands of lines of code. I recall seeing strategies to track opponent observed speed and direction so you can "lead" when shooting. It may be a long dig to find it, but I'm sure there are examples of such things out there.
http://robocode.alphaworks.ibm.com/home/home.html