Custom breadcrumbs makes use of the mysql mediumtext column type on the 'visibility_php' column, to store the php visibility settings. This is the case for all three custom_breadcrumb database tables that I have in my database (custom_breadcrumbs, custom_breadcrumbs_views and custom_breadcrumbs_paths). The column is included in every single lookup on those tables. That can mean 3 lookups per page.
Each of these lookups is unable to use MySQL's in memory table cache due to the inclusion of a TEXT field, and so temporary tables must be created on disk for each of these lookups. This results in a considerable performance issue - on every page. On disk temporary tables can have a massive effect on performance. I think that the general practice is to either not use text or blob columns, or move the TEXT/Blob data to a separate table, which allows you to do your lookup on the main table, utilising indexes and in memory temporary tables, and then join the blob data only if it's needed.
Please consider either changing these columns to varchar (perhaps this will be limiting on the amount of php that can used), making the use of php visibility settings an optional extra (I have no need for it) and/or moving the TEXT columns to a database table of their own.