ISR executes even though an interrupt is not triggered
After checking the queue functions that you use in your sketch, I see there is no protection against concurrent accesses in the enq and deq functions, which is a must-have if you use any of these functions from within an ISR.

I would suggest the simplest changes to these functions as follows:

void enq(TPrioQueue *queue, void *item, int priority)
{
    TPrioQEntry *newEntry=(TPrioQEntry *) malloc(sizeof(TPrioQEntry));

    if(newEntry != NULL)
    {
        newEntry-&gt;item=item;
        newEntry-&gt;prio=priority;
        newEntry-&gt;prev=NULL;
        newEntry-&gt;next=NULL;

        // Protect against concurrent accesses starting here
        uint8_t sreg = SREG;
        cli(); 
        if(queue-&gt;head==NULL)
            queue-&gt;head=newEntry;
        else
        {
            // Find insertion point.

            // First special case: Item at head has lower priority
            if(queue-&gt;head-&gt;prio &gt; newEntry-&gt;prio)
            {
                // Insert item at the start of the queue.
                newEntry-&gt;next=queue-&gt;head;
                queue-&gt;head-&gt;prev=newEntry;
                queue-&gt;head=newEntry;
            }
            else
            {
                // Find your insertion point
                TPrioQEntry *trav= queue-&gt;head;

                while(trav-&gt;next!=NULL &amp;&amp; trav-&gt;prio &lt; newEntry-&gt;prio)
                    trav=trav-&gt;next;

                newEntry-&gt;prev=trav;
                newEntry-&gt;next=trav-&gt;next;
                if(trav-&gt;next != NULL)
                    trav-&gt;next-&gt;prev=newEntry;

                trav-&gt;next=newEntry;
            }
        }

        queue-&gt;itemCount++;
        // Protect against concurrent accesses stops here
        SREG = sreg;
    }   
}

void *deq(TPrioQueue *queue)
{
    // Protect against concurrent accesses starting here
    uint8_t sreg = SREG;
    cli(); 
    // Return NULL if queue is empty
    if(queue-&gt;head == NULL)
    {
        // Protect against concurrent accesses stops here
        SREG = sreg;
        return NULL;
    }

    void *ret=queue-&gt;head-&gt;item;
    TPrioQEntry *tmp=queue-&gt;head;

    if(queue-&gt;head-&gt;next!=NULL)
        queue-&gt;head-&gt;next-&gt;prev=NULL;

    queue-&gt;head=queue-&gt;head-&gt;next;
    free(tmp);

    queue-&gt;itemCount--;

    // Protect against concurrent accesses stops here
    SREG = sreg;

    return ret;
}