Auto sorting as data is entered

I have asked for help on this question many times but no answer, So i came up with another idea, could this be done using VBA code.

The problem,

I have a sheet for entering data, that needs to be sorted, but there are some columns that are locked and the sheet is protected. At the moment i know that you cant sort across locked cells, so some data is not sorting.

So i thought that cos the data that needs sorting has a ref number that is could be sorted as the data is entered, by a set critiria.

I have attached a dummy sheet showing before and after, unfortunatley due to goverment policy, i can not post the actual sheet onto a public forum.
there is no formula within the sheet, it just shows how the data (top of sheet) is entered at first and the second table (bottom sheet) shows how it looks once sorted, This is what im trying to achieve automatically if possible.

it is sorted by service number first then destination. but if poss has to sort the comments cells as well, but these as you will see are the other side of the locked cells.

I hope i have explained it enuff for an answer.

Hope someone can help. Oh btw its Excel 2003 im using

Gareth