Even you wrote that you want to code everything yourself this time, you might want to consider to use a plugin for breadcrumbs, like (just to name one) Breadcrumb NavXT (WordPress Plugin).
If it does not support what you need out of the box, you will find a least all the code how it has been originally done and probably it offers ways to customize the breadcrumb path for you. And if it’s only to take a look how someone else is doing it.
As with your site, it looks to me that you’re intermixing different stuff wordpress has to offer while aiming for one thing: site structure. IMHO this has the tendency to make things complicated.
The menu in wordpress is not designed to actually structure your content nor is there anything else that allows you to high-level structure content. The only thing I’m aware of to provide structured content in a hierarchy, is to use pages with childs and parents. Next to that you can provide a same named and structured tree of post categories which can help to streamline both the page structure with posts you could add for pages (or merely then sections of your site).
But even with such a simplified approach, most breadcrumb plugins won’t work as they don’t expect to have pages their own posts.
I’m pretty sure that there is a solution for what you want to do, and as an additional tip on how to integrate that easily is by either creating a template tag for you breadcrumb path and/or a shortcode or widget you can easily distribute it on your site even when you change the logic behind your site’s structure.
And additionally, if you use the menu to structure your content, it should be possible to read that structure out and create a path out of it as it’s normally a tree structure and the breadcrumb is displaying the path to the current item. In the end you only need to add the current post at the end of it (Post23 in your example) if you’re on a single post page. That’s probably the easiest approach if you define your site’s structure within the menu.
Mtekk, the author of the breadcrumb plugin I named above is on this site as well, I bet he has some other valuable feedback for you.