Looks like you could easily use
Test::More::_deep_check to create
is_not_deeply and submit a PR. Of course, either you're the first person ever to need this or there's something fundamentally wrong with whatever it is that you're doing. Is there a reason you must do "is_not_deeply" when a test to make sure "is_deeply" would suffice? I'm still not quite sure what it is you're testing.
>I could just serialize a nested structure
If you can ensure consistent/ordered serialization in the case of your structures being hash refs (or use Tie::IxHash somehow, I suppose. But this doesn't seem to be the right approach if you're reaching for deeply comparing two structures. Consider that you'd probably need to write unit tests to test that your serialization is coming out as expected.