I see plum pollination as having multiple factors and these factors vary with each growing zone, so a cure all for poor pollination in my opinion doesn’t exist. Plums seem to need to be fairly mature, maybe 5 or 6 years too before drawing any conclusions. I have good pollination here, it took 5 years. I don’t have any native plums either. I don’t have a lot of trees either, Satsuma, Nadia and 4 pluots. All fruited this year, first time ever. Most were loaded with plums. I have added about 8 more as grafts this year, so I need another 5 years before I can make good observations on them.
In the colder zones Konrad knows his plums he is on Garden Web, and won’t come here. I’m not in a warm zone, but not in zone 3 either so my experiences in zone 5b/6a only apply to those zones and only in the Midwest in my opinion.
I think the fact I grow many plants that attract bees, and other beneficial made the most difference for me. Flowering herbs, nasturtium, borage, zinnia, sedums, lily’s, raspberries, etc. My yard is buzzing with bees all year. And they come back looking every year too. Many solitary bees probably live in the yard now. Some research does support that they help in stone fruit pollination. Nasturtium,columbine and borage self sow, only planted once. I germinate Zinnias every year, I really like them, the flower lasts for weeks and it produces ton’s of them. Easy to harvest seeds too. The others are perennials.
One of the biggest attracting plants to native bees I have observed is strawberries, native to all of North America. And they flower early, right with the plums.