It's because the Protection does not lock-in your styles only, it simply locks-out other ones (the ones you didn't choose). So, in Word 2003 you lock out styles like Table 1, Heading 1, etc. leaving only the ones you want remaining.
In Word 2007/2010, there are new styles that are part of the Quick Styles templates (like Bibliography, Intense Emphasis, etc.). You can find all Quick Styles templates in C:\Program Files\Microsoft Office\Office12\1033\QuickStyles (assuming you're using English, which is 1033) and C:\Documents and Settings(userID)\Application Data\Microsoft\QuickStyles (if the user has saved their own Quick Styles). It's a bit stupid, but because these were not locked out in Word 2003 explicitly, they are available to your Word 2003 document/template in Word 2007.
A macro may work here because your
ActiveDocument inherits Quick Styles in Word 2007 as its own. But you'd have to specifically name each of your own styles in a For/Next loop to add it to allow-in for restricted styles.
Another way to do this is to open one of these templates and copy the styles via the Organizer into a a new Word document in Word 2007, save that document as a Word 2003 document (.doc) and then in Word 2003 add these styles to the Normal.dot template. Then, open my Word 2003 document and disallow all of these newly added styles during restriction.