I've just been to two great game shops in the Isle of Wight.

Arcade Games in Shanklin is a real old school retro games shop. The guy who owns it is really friendly and knowledgable about retro games. He's got stuff piled floor to ceiling with plenty of games for older systems and is clearly passionate about gaming.

http://arcadegamesiow.com/

Outland is Ryde is a less of a retro shop (I couldn't see anything older than PS2) but is a nice alternative to CEX. They've also got a Neo Geo arcade machine with a multicart that is only 20p per credit.

http://www.outlandgamesvault.co.uk/