Shazam works much better than Midomi in my incredibly informal, anecdotal experiences... never got any of the extra midomi features to work when I could use them, either.
I think it's pretty well established that Midomi is faster and has better music recognition than Shazam. There's a few video comparisons out there that show this:
I reinstalled it based on your post and used it in Starbucks earlier, where it definitely worked better than Shazam.
Still can't recognize my humming, but that might be my fault more than Midomi's...