Are there any examples in classical texts where the word 'valde' is used before a superlative? For example 'valde stultissimus' to mean very, very stupid.
Georges’s Dictionary has references for valde optimus and valde summus from Pliny and Valerius.
No, valde can at most take a comparative adjective, not a superlative. However, "vel" can be used in your case. "vel" + a superlative is common in Latin literature, for example in Cicero's Pro Roscio Amerino:
vel potentissimus ... L. Cornelius Chrysogonus