After making three pages of notes, hours of thinking and in the end reading half of wikipedia, I got it done! 
I made a function that calculates exactly how to shoot at a target to hit it.
In the calculations it keeps track of gravity, the bullet speed and the speed of the target.

It should literally hit anything, as long as it moves with a constant speed! 

The function requires Jestermon's RadMath: http://www.3drad.com/forum/index.php?topic=4800.msg39902#msg39902

Put this above your script:
int MathDLLHandle=0;
float R_radians2degrees(float value)
{
   iDLLArraySet(0,value);
   iDLLCall(MathDLLHandle,"R_radians2degrees",0);
   float f = iDLLArrayGet(0);
   return f;
}
float R_atan(float value)
{
   iDLLArraySet(0,value);
   iDLLCall(MathDLLHandle,"R_atan",0);
   float f = iDLLArrayGet(0);
   return f;
}
void MathInitialize() {MathDLLHandle = iDLLLoad(".\\3DRad_res\\objects\\Script\\RadMath.dll");}
void MathDeInitialize() {if (MathDLLHandle != 0) iDLLUnload(MathDLLHandle);}


Vector3 AimFormula(Vector3 gunloc, Vector3 targetloc, Quaternion targetrot, float bulletspeed, float targetspeed, float gravitation)
{
   float Distance = iVectorLength(targetloc-gunloc);
   float BulletOffset = (Distance / bulletspeed) * targetspeed;
   Vector3 OffsetLoc, AimLoc;
   iVectorRotate(OffsetLoc,Vector3(0,0,BulletOffset),targetrot);
   AimLoc = OffsetLoc+targetloc;
   Vector3 unRotAimLoc;
   Quaternion LookRot;
   iQuaternionLookAt(LookRot,AimLoc-gunloc,Vector3(0,1,0));
   float xRot,yRot,zRot;
   iQuaternionToEulerAngles(LookRot,xRot,yRot,zRot);
   if (xRot >= -90 && xRot <   90) xRot = 0; if (xRot >= 90  && xRot <  180) xRot = 180; if (xRot <= -90 && xRot > -180) xRot = -180;
   if (xRot !=  0) yRot = 180-yRot;
   if (yRot > 180) yRot -= 360;   
   Quaternion InverseRot;
   iQuaternionFromEulerAngles(InverseRot,0,-yRot,0,"xyz");
   iVectorRotate(unRotAimLoc,targetloc-gunloc,InverseRot);
   float v2 = iFloatAbs(bulletspeed*bulletspeed), g = iFloatAbs(gravitation), x = unRotAimLoc.z, y = unRotAimLoc.y;
   if (v2 == 0) v2 = 0.000000000001; if (g == 0) g = 0.000000000001; if (x == 0) x = 0.000000000001; if (y == 0) y = 0.000000000001;
   float TanAngle = (v2-iFloatSqrt((v2*v2)-g*(g*(x*x)+2*y*v2)))/(g*x);
   float AimAngle = R_radians2degrees(R_atan(TanAngle));
   if (AimAngle < 0 || AimAngle > 90) AimAngle = 45;
   return Vector3(-AimAngle,yRot,0);
}
An example: http://www.3drad.com/forum/index.php?action=dlattach;topic=9404.0;attach=15804

Hope it helps!