I couldn't agree more. I've been researching this for the last couple of days and it looks like it should be fairly easy to implement. There are a number of videos on youtube which say that using NavXT can produce breadcrumbs which Google recognises, e.g.:
This is true - but in so far as it produces markup which is the same on each page. Most breadcrumb plugins theoretically should do this.
If there was a way that plugin authors (e.g. Yoast breadcrumbs; Justin Tadlock's Breadcrumb Trail) could add an option to add variables *before/after* each item on the trail, then this would work...