As well as payslips, you should have had a P60 at the end of each tax year. This should show the gross pay and the amount of tax and national insurance you paid in the year.
If you can find the P60 for 06-07 then it should show whether they deducted NI. If they did not, then - unless your weekly pay was very low - they have broken the law. If they did, and did not then pay it over to HMRC they have broken the law. If they told you they didn't start paying NI till 7/07 something seems to be wrong - all employers have to deduct NI & pay it over to HMRC for each employee who earns more than the lower earnings level each week.