This sentence would also work without the valde, right? What is that "valde" anyway?
Valde is the very in the English sentence.
It is an adverb, valide or valde "strongly", derived from validus "strong".
Is 'nos' actually needed for this as it seems implied with esurimus.
No, it is not needed. Is sine dubio valde esurimus not accepted?