Well, increasing the memory limit doesn’t necessarily mean that the two plugins (either individually or through some interaction) eat up a lot of memory. You said at first it worked, and then eventually you ran into issues. What happened between when you initially set things up and when things stopped working? Did you activate any other plugins?
To really get a grasp of what’s going on you’re going to need to do more testing. Ideally, you’d find the rough amount of memory that is needed where the site still works (but a little less causes the site to not work) for four cases (WordPress only, WordPress + Breadcrumb NavXT, WordPress + WP SEO by Yoast, and then WordPress + Breadcrumb NavXT + WP SEO by Yoast). With that information you will be able to determine if one of the two plugins is using a lot of memory, if an interaction between the two is causing increased memory usage, or if it is something else. While running these tests, I’d deactivate all other plugins to prevent possible interactions.
Breadcrumb NavXT should not use too much memory (though to be honest I haven’t measured it recently). Most of the time it should be operating on data that is already stored within the WordPress session (already cached, so the bulk of the memory ‘used’ by Breadcrumb NavXT was already used). I do try to improve performance with new releases, though I typically do not advertise these improvements.