Can the Drupal 6 search function also index block content?
No, block content is not searchable by default.
Have you tried the Block Search module? Seems that is what you need.

edit: After reviewing the module, I now see that the search functionality inside block content is done for only administrators, so that module probably doesn't help.