How do I clear all the personal / sensitive data from CiviCRM DB via SQL?
As people have pointed out there is a very comprehensive answer to the question of anonymising data, however this questions was about simply clearing data.

The correct answer from Pete and Demerit was that I had missed the sort_name column from the civicrm_contact table. So the full SQL is now:-

delete from civicrm_email; 
delete from civicrm_address; 
delete from civicrm_phone;
update civicrm_contact set birth_date = NULL; 
update civicrm_contact set first_name = 'Staging';
update civicrm_contact set middle_name = '';   
update civicrm_contact set last_name = concat('Test',id);
update civicrm_contact set legal_name = ''; 
update civicrm_contact set display_name = concat('Staging Test',id); 
update civicrm_contact set sort_name = concat('Staging, Test',id); 
update civicrm_contact set addressee_display = 'Dear Staging';
update civicrm_contact set email_greeting_display = 'Dear Staging';
update civicrm_contact set postal_greeting_display = 'Dear Staging';


And as pointed out by @Chris you will also need to clear the cache tables, but please use the GUI for this as direct SQL on these tables can cripple the CiviCRM caching logic.

Feel free to edit and expand this answer if you know of any other fields that can be cleared by SQL.