There are numerous possibilities for cold-hardy palm hybrids for our region.
As mentioned, Phoenix species are known to hybridise with each other very readily. Perhaps someday a cross could be made between P. atlantica X P. rupicola or some such thing, to result in a much more tropical looking hardy palm. The possiblities in this genus are numerous, but the Pacific Northwest is probably too far north for Phoenix to ripen fruit. How about P. dactylifera X humilis, P. atlantica X sylvestris, or P. theophrastii X taiwaniana.
Washingtonia filifera is thought to hybridise with W. robusta, producing a hybrid called W. X 'filibusta'. Some people would swear that these hybrids all all over Texas, while others would swear that environmental factors and genetic variation account for all the differences and there is really no such thing as a hybrid. I'm not really qualified to comment.
It might be possible to cross Nannorrhops X Corypha, resulting in something that would be worth trying. Corypha is cold-tender, but has unearthly proportioned, enormous leaves.
Butia, Jubaea, Syagrus, Parajuabea and probably also Lytocaryum can all be hybridised with each other. The most common of these is Butia capitata X Syagrus romanzoffianum (called 'X Butiagrus'), which is a variable palm in its appearance and cold-hardiness (both parents are variable to begin with), but always superior to both parents, being more tropical looking than either, more cool tolerant and cold hardy than Syagrus and faster growing than Butia. The next most common hybrid (though very rare) is Butia X Jubaea, which is of great interest, looking very attractive and being faster growing than Jubaea while hardier than Butia. Then consider that we have three distinct forms of Jubaea to potentially work with, 8+ species of Butia (as well as many variants of B. capitata), 4 Parajubaeas, who-knows-how-many species of Syagrus and possibly Lytocaryum to work with, and it would seem that we could be busy hybridising for a couple hundred years to come up with the perfect palm. Cocos is also related to these other palms, but attempts to hybridise it with anything have not been successful.
Trachycarpus species can also be crossed, with some limits. T. wagnerianus is known to hybridise with T. fortunei, and certainly T. takil also could. It is not known whether some of the other species are as compatible; my guess would be that most of them are except T. martianus and T. latisectus which could be crossed only with each other. But we do not really know this. T. martianus X fortunei hybrids have been reported, but I doubt they really exist. In any case most of these rare species of Trachycarpus are so intriguing by themselves, it is hard to imagine a hybrid would yield something superior. Trachycarpus is closely related to Guihaia, and it is not out of the question they might hybridise. Some have attempted to cross Trachycarpus with Rhapidophyllum, but without success.
There are probably quite a few other possibilities I have not thought of.