Throwing up an answer here because Rock 'n Roll racing is one of the best games of all time. That being said...
From your wording here it sounds like the task you are measuring that absolutely must make its deadline is the lowest priority. That right there is backwards. You want your task that needs to be guaranteed its completion as the highest priority task.That would be step one. If I am mistaken from how I read your question and your thread that needs to make those deadlines is the highest priority then there are other things to look at.
Make sure interrupts are not disabled by any of the other tasks for extended periods since that will effect the thread scheduling. If a low priority task is disabling interrupts and then spinning in a loop for a while there is no way for the RTOS scheduler to take back control and give it to your high priority thread.
Check for priority inversion (http://en.wikipedia.org/wiki/Priority_inversion). If there is resource sharing between your low priority thread and this critical thread then you can get into a case where even though your critical thread is high priority it might block waiting for a lower priority thread to finish using a resource. Not sure if FreeRTOS has priority mutexes/semaphores but that is something you can check as well.
Another thing which is probably the simplest explanation is to profile the thread. This is difficult to do on embedded systems but you can make some sort of light logging buffer or something of that sort. Find out when it's sometimes missing its deadline what is different about that code path vs the times it makes it ok. You might have to find a way to speed up some of that path. For instance in a slow run it could be writing a larger amount of data than normal so maybe change those data writes to use DMA instead of the thread manually writing.
This is not an exhaustive list but some good tips to get started.