You'd want to take a look to Mage_Catalog_Block_Breadcrumbs class, catalog breadcrumbs path is built in _prepareLayout()
method, you can compare the code with same method in Mage_CatalogSearch_Block_Result class
One way to achieve this could be:
Rewrite Mage_CatalogSearch_Block_Result class, so you can store in session label, title & url of the search result page to use it later
Rewrite Mage_Catalog_Block_Breadcrumbs class, and then check referer url (Reliable way to redirect to last page), if it's a search result url then you should modify breadcrumbs path, to include the stored in session search path
Something like this...
protected function _prepareLayout()
{
if ($breadcrumbsBlock = $this->getLayout()->getBlock('breadcrumbs')) {
$breadcrumbsBlock->addCrumb('home', array(
'label'=>Mage::helper('catalog')->__('Home'),
'title'=>Mage::helper('catalog')->__('Go to Home Page'),
'link'=>Mage::getBaseUrl()
));
if ($product = Mage::registry('current_product')){
// check referer url to see if you come from a search result page
// get your stored in session search string, and include it
$breadcrumbsBlock->addCrumb('XXXX', array(
'label'=> XXXX
'title'=> XXXX
'link'=> XXXX
));
}