What’s the best way to display hierarchical tabular data (parent/child relationship) while allowing both pagination and search?

I've run into a brick wall while trying to come up with a suitable tabular user interface for showing hierarchical data in a table while at the same time including a search interface and pagination.

The basic structure of the table might look something like this:

The user has access to a pagination interface (lower right hand corner) to break up large data-sets as well as a search feature (at top) to search the records.

One of the problems I'm facing is how I should handle the displaying of child rows when it comes to pagination. Should I count the child rows ('case fans, thermal compoints, etc...') when displaying X amount of records per page? My instincts tell me not to count the children because if the user switches pages they will lose context of the parent record they are looking at. Additionally, if I keep the child rows hidden by default (unless the user clicks a "plus" icon next to a parent), it should keep the table more compact. However, by not counting the child records in the total, then the user doesn't know how many total records were returned int he query (i.e. the bottom of the table would say, "Showing 1 Record" when in fact there are 20 additional child records in the table)

Another problem I'm facing is how to display search results in the table if a child matches the search and the parent does not. Additionally, I want to know if I should include all children of a matching parent.

For example, if the user types in the word "case" in the search box, I could return the results like this:

The user sees all matches for case within the context of the hierarchy. However, in the event that child records are hidden by default, it might look like "Computer Hardware" was a match to the search. Using this method I would have to show all child rows by default thus stretching the size of the table.

Another option might be to eliminate the hierarchy altogether. This solves both the pagination issue and the search results issue. However the downside of doing this is that the user loses all context of the parent/child relationship between records.

Finally, I'm curious if when running a search like "Computer Hardware" that returns a parent category if I should automatically include all children for the match. While technically the child records don't have a matching string in their title, they still are related to the match because they exist as children of the parent.

Any insight, ideas, or inspiration you might have on this subject would be most appreciated. Areas I've searched for inspiration include the jQuery datatable plugin and the Apple OS X Finder interface.