"I mean, they do allow their search to work just fine without Javascript, so why not the logo too?"

a) The site still works with Javascript turned off.

b) The logo is degraded.

So how is this not graceful degradation?