You can use the normal search service (same as the front-end search uses). This means you have a fuzzy / full-text search using Lucene, and all parts can participate in indexing (including BodyPart). The big disadvantage is it's not very good at partial
I've been thinking about this myself and I even started building a module (it's largely unfinished tho). I wanted to reduce redundancy by creating a search that would replace the front-end search, and be used in the back-end, and have a "pop-up search" mode
which you could use for selecting content (for creating relationships, etc.)
I wanted to aggregate multiple searches; so as well as the Lucene query, you could also do a LIKE query on BodyPart to get partial-word matches. However it might just be better to implement a custom search provider for this.
I was also considering trying to reuse some of Sebastien's Projections work to try and achieve this.