How to produce a highly accurate phase or frequency shift at 500 MHz?
There are vector phase shifter/modulator devices on the market.  Basically, you generate a fixed shift (ideally around 90 degrees, but not critical) and then proportionally add/substract the original and fixed-shift phases to produce any desired output phase.

Getting best performance (especially if the fixed shift is not 90 degrees) would require using DACs to generate the control voltages for each phase from a lookup table based on measurements previously taken at a particular frequency (or automatically over a range of frequencies, perhaps using a GPIB-connected vector network analyzer)

RE-EDIT: Since you have a solution at low frequencies, one option is to just mix each of these up to 500 MHz using the same local oscillator and pass the outputs through matched band filters.  This is slightly more practical if you use arbitrary generators capable of outputting a higher frequency, say 100 MHz, as then the filter requirements are looser.  Ultimately this is sort of reshuffling of the same idea - it's still multiplication, but your control inputs are moderate frequencies instead of DC voltages and it moves the shifting requirement through the multiplier to where it is easy, at the cost of requiring some filters on the other side.  And there's even a form where you replace the filters with a quadrature (2-phase) local oscillator and image reject mixers.

ADDITIONAL IDEA:

A pair of lower frequency linked generators could be used as references for PLL synthesizers multiplying to the desired frequency range.  Changing the phase of the low frequency signal will result in a phase change of the high frequency one, of magnitude multiplied by the multiplication factor (think of the phase change as a time delay, with which the higher frequency signal must also align).  The catch is that extremely fine control of phase would be necessary at the low frequency to get moderate resolution control at the higher one.  For example, if you have a 20 MHz signal synthesized at 100 MSPS, a delay of one sample is 5 entire periods of a 500 MHz product!   As a result, this would require a DDS with many bits of residual phase - that is to say, less significant bits of the phase accumulator that accumulate internally, and only eventually roll over into the bits that are of a high enough order to feed into the lookup table that generates sine samples.  Any decent DDS has some of these; in this case you'd need an extreme.  The idea probably works best when the DDS frequency is as high as practical - ie a few hundred MHz clocked at a gigasample (which is something you've been able to buy as an IC from Analog Devices etc for a few years now) and the PLL multiplication ratio is fairly low.

Most of these ideas seek to use a greater quantity of relatively inexpensive (per unit) active circuitry and even software to limit the requirement of expensive per-unit-adjusted precision passive elements.  Unfortunately, most require pairs of filters or a shift network with performance that is either similar, or been per-unit characterized so that its imperfections can pre-compensated in the control settings used.  The method using two low frequency DDS's and image reject mixers goes closest to avoiding this, but it needs near perfectly orthogonal quadrature LOs at fixed frequencies for each band - for example 400 MHz to mix to the 500 MHz band.  It may be possible to create two phases by digitally dividing from a higher frequency, otherwise there would be a shift element that would need to be aligned for each band of interest.  The soundcard-as-HF-exciter ham software-defined-radio people have done some looking at precompensating the synthesized signals to compensate for imperfect IQ LOs and mixers which could be looked into, but since the idea is to have perfect cancellation of the image frequency (vs filter it out) this is pretty critical.

Simple answer if $$ available

If budget permits, Agilent and presumably others offer dual channel and synchronizable arbitrary waveform generators that will do 500 MHz either directly or via an IQ mixer.  As an off the shelf solution, this would be closest to extending what you are able to do at 20 MHz to the 550 MHz need.  Such equipment is rented as if not more often than purchased outright.