Would you trust a pre-flashed phone though?

I guess with GOS they have integrity checkers.

I could have sworn they had plans to ship Graphene phones

They do. They say it in their roadmap:

Hardware and firmware security are core parts of the project, but it's currently limited to research and submitting suggestions and bug reports upstream. In the long term, the project will need to move into the hardware space.

https://grapheneos.org/faq#roadmap

There are some third party vendors online that ship pre-flashed GrapheneOS phones iirc, but I don't believe there has ever been on with it factory installed.