As Mattias has noted, this commit on markdown-mode did fix the issues, it would still be nice to know why the natively compiled version behaves differently from the byte compiled version tho. This could be good learning for occasional elisp devs such as myself to know what to watch out for.

https://github.com/jrblevin/markdown-mode/commit/44f0e89534e6e5b3e752759d513f4a6f9757b9ee
On 18 May 2023 at 8:54 AM +0100, Andrea Corallo <akrl@sdf.org>, wrote:
> Eli Zaretskii <eliz@gnu.org> writes:
>
> > > From: Jimmy Yuen Ho Wong <wyuenho@gmail.com>
> > > Date: Thu, 18 May 2023 03:40:40 +0100
> > >
> > >
> > > Users have discovered there's a markdown-mode function that behaves
> > > differently depending Emacs is executing byte-compiled code or natively
> > > compiled code.
> > >
> > > The issue is documented
> > > [here](https://github.com/jrblevin/markdown-mode/issues/578).
> > >
> > >
> > > There are two examples in the issue that will produce an `Wrong type
> > > argument: consp, nil` error on the natively compiled version of
> > > `markdown-imenu-create-nested-index`, but not the byte-compiled or
> > > interpreted version. A user has provided a disassembly of the natively
> > > compiled code for that function.
> > >
> > > The last user has said and I can confirm the offending line seems to be `(setcdr
> > > sibling-alist alist)` in that function.
> > >
> > > Much appreciate it if Andrea could take a look.
> >
> > Adding Andrea.
> >
> > While, of course, Andrea's help will be appreciated, there's currently
> > no reason to believe this is a problem in the Emacs core, and
> > therefore filing a bug report here could be premature. Ideally, the
> > markdown-mode's developers should examine the problem first and
> > present convincing evidence that this is a problem with native
> > compilation and not with the code in markdown-mode itself.
>
> Yep, if markdown-mode's developers could present a reproducer showing
> how exactly the function miss-behaves and where that would help.
>
> Andrea