I've copied and pasted the html verification code into my Misc script section in Design tab and cleared my cache etc, but when I attempt to verify it doesnt work, I've also looked for the validation code in my source code, but no sign of it. So this is most likely the problem but any ideas on how to fix it?
Is it possible to share the public url of your store?
Your code should be visible here:
You can add the code at: System -> Configruation -> Design -> Header HTML -> Miscellaneous Scripts
Then clean cache and should be working.
Well... as you saw there isn't an special step or configuration.
Maybe you can try using RWD theme for a moment? (I guess this shouldn't happen but... who knows).
Which type of cache are you using? (something like Redis or just the file cache provided by Magento?)