melange should test a package using package.full-version and not just the package name. I noticed this was a problem with freerdp, which is version 2.., but the test in freerdp.yaml was actually using just the package name so the solver choose freerdp-3 as it provides freerdp. This is obviously problematic because we are not testing the package we thought we were.
I resolved this by adding freerdp=${{package.full-version}} to the package test (https://github.com/wolfi-dev/os/pull/69542/files) but @justinvreeland suggested melange should actually do this by default.
As an aside - I'm scared about what other packages we might be testing but not really testing!