Stával na Vyšehradě skutečně hrad? Jsou po něm nějaký pozůstatky?

Ano,stával.
http://www.sta­rapraha.cz/his­torie-praha-vysehrad.php

Z nejstarší doby byly zjištěny četné zbytky keramiky na různých místech návrší, pozůstatky dřevohlinitých valů s čelní kamennou zdí na severním okraji v dnešních Karlachových sadech. Nejvýznamnějším nálezem jsou základy mohutného čtvercového kostela se třemi apsidami pod zbytky pozdější baziliky sv. Vavřince, dochovanými v objektu nynějšího Starého děkanství. Všechny tyto nálezy, stejně jako písemné prameny, nasvědčují, že Vyšehrad je zhruba o jedno století mladší než Pražský hrad. Přesný průběh opevnění z této doby nelze vzhledem k míře pozdějších terénních změn určit, rozloha hradiště bývá odhadována na 9 až 10 hektarů. Původně zde měl být domnělý hrad „Chrasten“ – „jejž nynější lidé nazývají Vyšehrad (Wissegrad), tehdy však od chrastí dostal jméno Chvrasten (Hvrasten)“

Zdroj: https://cs.wi­kipedia.org/wi­ki/Vy%C5%A1eh­rad