Android Alarm not triggering at exact time

Question

I have a problem using AlarmManager to run an IntentService at an exact interval. First i want to mention that i know about the changes to alarms since API level 19 and i have a proper way of handling things:

public static void setServiceAlarm(Context con, long offset, boolean isOn, long lastHandledStamp){
    Intent i = new Intent(con, StService.class);
    Bundle extra = new Bundle();
    extra.putLong(EXTRA_TIMESTAMP, lastHandledStamp);
    i.putExtras(extra);

    PendingIntent pending = PendingIntent.getService(con, 0, i, PendingIntent.FLAG_UPDATE_CURRENT);

    AlarmManager manager = (AlarmManager) con.getSystemService(Context.ALARM_SERVICE);
    if (isOn){
        if (Build.VERSION.SDK_INT < 19) {
            //for versions 19 and above all repeating alarms are inexact
            Log.i(TAG, "Version below 19, setting repeating alarm");
            manager.setRepeating(AlarmManager.RTC, System.currentTimeMillis(), INTERVAL, pending);
        } else {
            manager.setExact(AlarmManager.RTC, System.currentTimeMillis() + offset, pending);
        }
    } else {
        manager.cancel(pending);
        pending.cancel();
    }
}

This is what i use to set an exact alarm. However this doesn't seem to be working. I am running API 22 and in my IntentService i log when the service runs. It's supposed to run every 15 seconds and this is what i get

10-12 14:14:30.018 9864-11782/com.jam.dragbot I/StService: onHandleIntent
10-12 14:15:00.018 9864-12241/com.jam.dragbot I/StService: onHandleIntent
10-12 14:15:20.028 9864-12547/com.jam.dragbot I/StService: onHandleIntent
10-12 14:15:36.021 9864-12777/com.jam.dragbot I/StService: onHandleIntent
10-12 14:16:00.021 9864-13174/com.jam.dragbot I/StService: onHandleIntent
10-12 14:16:37.705 9864-13810/com.jam.dragbot I/StService: onHandleIntent
10-12 14:17:00.025 9864-14124/com.jam.dragbot I/StService: onHandleIntent
10-12 14:17:15.307 9864-14342/com.jam.dragbot I/StService: onHandleIntent
10-12 14:18:00.019 9864-14994/com.jam.dragbot I/StService: onHandleIntent
10-12 14:19:00.018 9864-15898/com.jam.dragbot I/StService: onHandleIntent
10-12 14:19:25.933 9864-16264/com.jam.dragbot I/StService: onHandleIntent
10-12 14:20:00.016 9864-16759/com.jam.dragbot I/StService: onHandleIntent
10-12 14:20:15.281 9864-16973/com.jam.dragbot I/StService: onHandleIntent
10-12 14:20:30.570 9864-17197/com.jam.dragbot I/StService: onHandleIntent
10-12 14:21:00.020 9864-17647/com.jam.dragbot I/StService: onHandleIntent
10-12 14:21:17.982 9864-17915/com.jam.dragbot I/StService: onHandleIntent
10-12 14:22:00.021 9864-18589/com.jam.dragbot I/StService: onHandleIntent

As you can see the service is started at random intervals, which is unacceptable in my case. What is the problem and how can i fix it?