Try (from Companies House) :
EBAY (UK) LIMITED
50 VICTORIA EMBANKMENT
LONDON
EC4Y 0DX
They're slippery little things (which makes me dubious of their UK presence), however a little further research shows the above address is a buisness centre - another company with that address has the following number, so I'm guessing if you ring that you might get the central switchboard (where asking for ebay might work?!) :
020 7353 1234
Either way, that Companies House record shows that "Ebay (UK) Limited" used to be called "LAW 1044 LIMITED" - now how dodgy is that?!?!