check this



If audio CDs do not play automatically when you use these steps, use the following steps:

1.Click Start, point to Settings, click Control Panel, and then double-click System.

2.On the Device Manager tab, double-click CD-ROM, and then double-click the
entry for your CD-ROM.

3.On the Settings tab, click to select the Auto Insert Notification check box.

4.Click OK, click Close, and then click Yes when you are prompted to restart your
computer.

 

I should have been more specific...
Program (games etc.) CDs don't autoplay (I believe music ones still do....).
Also, all the things you mentioned are already in place

 

Try Autorun.zip from here. Once it's downloaded, unzip it and then double left click on the .reg file to apply it.

Let us know what happens.