The version in the tools repository is a bit old and doesn't have ARM support (it's meant for scratchbox X86 use only). There's a valgrind-3.6.0 in extras-devel which you can try though.
I'm just puzzled why entering "valgrind" into the search field of maemo.org didn't return the link you posted. Or let me put it this way: I didn't find an easy way to go to http://maemo.org/packages. Is it linked somewhere?
I only checked "garage.maemo.org" for software
Entering "n900 valgrind" or "maemo valgrind" into google didn't return any useful results, too.