Sachverhalt:
A. X._ (geb. xxxx 1940) trat am 15. Oktober 1968 im Rahmen eines Strafverfahrens in die Psychiatrische Klinik A._ ein, nachdem er in St. Gallen grundlos mehrere Passanten angegriffen hatte. Am 17. Juni 1969 wurde er zufolge Unzurechnungsfähigkeit von der Anklage der einfachen Körperverletzung und der Tätlichkeit freigesprochen und gestützt auf Art. 14 aStGB in der Psychiatrischen Klinik A._ verwahrt, wo er seither lebt.
Am 5. November 1999 verfügte der Bezirksarzt-Stellvertreter B._ und A._ die Rückbehaltung von X._ in der Psychiatrischen Klinik A._ im Rahmen einer fürsorgerischen Freiheitsentziehung (FFE). X._ stellte in der Folge verschiedene Entlassungsgesuche, die jeweils abgewiesen wurden.
B. Am 29. Januar 2010 stellte X._ erneut ein Entlassungsgesuch, das von der Klinikleitung am 3. Februar 2010 abgewiesen wurde. Die hiergegen erhobene Beschwerde wies die Verwaltungsrekurskommission des Kantons St. Gallen mit Entscheid vom 18. Februar 2010 ab.
C. Gegen diesen Entscheid hat X._ am 26. April 2010 eine Beschwerde in Zivilsachen eingereicht mit den Begehren um dessen Aufhebung und Feststellung, dass die FFE vom 5. November 1999 nicht mehr besteht, eventualiter um deren sofortige Aufhebung, subeventualiter um Rückweisung der Sache an die Verwaltungsrekurskommission. Ferner wird die unentgeltliche Rechtspflege und der Zuspruch einer Entschädigung von Fr. 3'783.-- verlangt. Es wurden keine Vernehmlassungen eingeholt.

Erwägungen:
1. Angefochten ist ein letztinstanzlicher kantonaler Entscheid (<ref-law>) betreffend fürsorgerische Freiheitsentziehung, gegen den die im Übrigen rechtzeitig erhobene (Art. 46 Abs. 1 lit. a und Art. 100 Abs. 1 BGG) Beschwerde in Zivilsachen gegeben ist (Art. 72 Abs. 2 lit. b Ziff. 6 BGG).
Nicht einzutreten ist auf die Beschwerde, soweit nicht nur die FFE als solche, sondern sinngemäss auch die Zwangsmedikamentation in Frage gestellt wird. Hierauf ist die Verwaltungsrekurskommission unter Verweis auf die diesbezügliche Rekursmöglichkeit an das Gesundheitsdepartement nicht eingetreten, ohne dass der Beschwerdeführer dies anfechten oder in Frage stellen würde.
Während das Bundesgericht die Rechtsanwendung im Rahmen genügender Vorbringen (<ref-law>) frei überprüft (Art. 95 i.V.m. <ref-law>), ist es an die kantonalen Sachverhaltsfeststellungen gebunden (<ref-law>). Diesbezüglich kann einzig eine willkürliche Sachverhaltsfeststellung oder eine anderweitige entscheidwesentliche Verfassungsverletzung gerügt werden (<ref-law>; <ref-ruling> E. 7.1 S. 398), wofür das strenge Rügeprinzip gilt (<ref-law>).
Auf die Beschwerde kann deshalb nicht eingetreten werden, soweit der Beschwerdeführer den Sachverhalt aus eigener Sicht schildert bzw. vom angefochtenen Entscheid abweichende Sachverhaltsbehauptungen erhebt, ohne jedoch hinsichtlich der Sachverhaltsfeststellung eine Verletzung von verfassungsmässigen Rechten zu rügen; darauf wird im Sachzusammenhang zurückzukommen sein.
2. Der Beschwerdeführer macht geltend, dass die am 5. November 1999 angeordnete FFE mit dem Übertritt in das Pflegeheim C._ dahingefallen sei und für die Rückverlegung auf die geschlossene Station 9/1 per Ende 2009 eine neue FFE-Verfügung unabdingbar gewesen wäre.
2.1 Die Verwaltungsrekurskommission hat festgehalten, dass die Psychiatrische Klinik A._ in drei Fachbereiche unterteilt ist: Akutpsychiatrie, Sucht- und Psychotherapie - Gerontopsychiatrie, Langzeitpsychiatrie und Forensik - Pflegeheim C._. Die Fachbereiche sind in verschiedenen Gebäuden auf dem gleichen Gelände untergebracht und sie unterstehen derselben Leitung. Im Verlauf des Jahres 2009 wurde der Beschwerdeführer von der Station 9/3 auf die Station 9/1 verlegt, nachdem er einem Mitbewohner ein Glas auf den Kopf geschlagen hatte. Am 17. November 2009 wurde er probeweise in das offen geführte Pflegeheim C._ verlegt, welches im Nachbarhaus untergebracht ist. Weil er dort seine Medikamente nicht mehr einnahm bzw. bereits vorher die Einnahme nur vorgetäuscht hatte, kam es erneut zu Gewalttätigkeiten, worauf er Ende 2009 wieder auf der geschlossenen Station 9/1 untergebracht wurde.
2.2 Die Verwaltungsrekurskommission hat befunden, dabei habe es sich um eine Verlegung des Beschwerdeführers innerhalb der Klinik und damit innerhalb der gleichen Anstalt gehandelt. Nach der glaubhaften Darlegung der stellvertretenden Chefärztin habe zu keinem Zeitpunkt eine Entlassung aus der FFE stattgefunden. Der Beschwerdeführer habe sich auch im Pflegeheim C._ weiterhin im Patientenstatus befunden und die laufende Krankengeschichte sei nahtlos fortgeführt worden.
2.3 Ein Streit um Worte ist, wenn der Beschwerdeführer dafür hält, er sei nicht in das Pflegeheim C._ "verlegt" worden, sondern es habe sich um einen "Übertritt" gehandelt. Von der Sache her bestreitet er den geschilderten Sachverhalt nicht (gleiche Klinik, gleiche Leitung, gleicher Patientenstatus, gleiche Krankengeschichte). Er macht jedoch geltend, während der eineinhalb Monate im Pflegeheim C._ habe er sich grundsätzlich frei bewegen und mit der Aussenwelt Kontakt aufnehmen können. Deshalb sei der FFE vom 5. November 1999 zwar nicht explizit, wohl aber faktisch aufgehoben worden und bestehe somit nicht mehr.
2.4 Das Vorbringen des Beschwerdeführers, die Rückverlegung auf die Station 9/1 wäre nur mit einer erneuten Einweisungsverfügung möglich gewesen, scheitert nicht nur daran, dass er nie aus der FFE entlassen worden ist, wie er im Übrigen selbst einräumt, sondern insbesondere auch am Umstand, dass er gegen die Rückverlegung per Ende 2009, womit in seinen Augen faktisch wiederum eine FFE verfügt worden wäre, keine Beschwerde eingereicht hat. Auf die Rückverlegung als solche kann demnach im Rahmen der vorliegenden Beschwerde, deren Anfechtungsobjekt allein der abschlägige Entlassungsentscheid der Klinikleitung vom 3. Februar 2010 ist, nicht mehr zurückgekommen werden. Beschwerdethema kann mit anderen Worten nur sein, ob der Beschwerdeführer zurzeit rechtmässig in der Klinik zurückbehalten wird (<ref-law>) oder ob er zu entlassen ist (<ref-law>).
3. Der Beschwerdeführer macht denn auch geltend, dass die materiellen Voraussetzungen für eine Rückbehaltung in der Klinik nicht gegeben seien.
3.1 Eine mündige oder entmündigte Person darf wegen Geisteskrankheit, Geistesschwäche, Trunksucht, anderen Suchterkrankungen oder schwerer Verwahrlosung in einer geeigneten Anstalt untergebracht oder zurückbehalten werden, wenn ihr die nötige persönliche Fürsorge nicht anders erwiesen werden kann (<ref-law>). Wie bei der Einweisung in eine Anstalt ist auch bei der Zurückbehaltung des Betroffenen das Prinzip der Verhältnismässigkeit zu beachten. Erforderlich ist, dass der Betroffene infolge der im Gesetz umschriebenen Schwächezustände persönlicher Fürsorge bedarf, die ihm nur in einer Anstalt gewährt werden kann (<ref-ruling> E. 5 S. 217). Ferner ist die Belastung zu berücksichtigen, welche die Person für ihre Umgebung bedeutet (<ref-law>). Sobald es sein Zustand erlaubt, muss der von der fürsorgerischen Freiheitsentziehung Betroffene entlassen werden (<ref-law>; zum Ganzen: <ref-ruling> E. 4 S. 292).
3.2 Nach den tatsächlichen Feststellungen der Verwaltungsrekurskommission leidet der Beschwerdeführer an einer chronisch paranoiden Schizophrenie mit wahnhaften Residualsymptomen. Er hat häufig Angst und fühlt sich bedroht, namentlich auch im sexuellen Bereich. Er führt einen Kampf gegen das Böse und um seine Sexualität. Mit Schlägen will er anderen Leuten das Böse austreiben. Insbesondere wenn der Beschwerdeführer seine Medikamente nicht einnimmt (wie im Pflegeheim C._), kommt es zu Gewalttätigkeiten und Übergriffen, die nach den Feststellungen der Verwaltungsrekurskommission unberechenbar auftreten und psychotisch bedingt sind. Die Gewalttätigkeit trat seit je in Erscheinung. In jüngerer Zeit sind folgende gravierenderen Vorkommnisse dokumentiert: Auf der Station 9/3 schlug der Beschwerdeführer vor ungefähr einem Jahr einem Mitinsassen, den er für einen Satanisten hielt, ein Glas auf den Kopf, worauf er auf die geschlossene Station 9/1 verlegt wurde. Sodann kam es im Pflegeheim C._ wiederum zu Vorfällen. Dort ging er am 29. November 2009 tätlich auf einen Mitbewohner los; ein weiterer Vorfall ereignete sich am Folgetag. Am 5. Januar 2010 erklärte der Beschwerdeführer, es sei normal, dass er schlage oder Tritte versetze. Am 8. Januar 2010 ging der Beschwerdeführer auf einen Tagespatienten los. Am 10. Januar 2010 waren zwei gewalttätige Ausbrüche gegen eine Bezugsperson und gegen einen Patienten zu verzeichnen. Am 12. Januar 2010 belästigte er bei einem Ausgang ein elfjähriges Mädchen. Seither hat der Beschwerdeführer wieder eine sehr engmaschige Kontrolle. Er hat pro Tag zweimal eine halbe Stunde Ausgang und darf sich nicht vom Klinikgelände entfernen. Die übrige Zeit muss er sich auf der geschlossenen Abteilung aufhalten, wobei der Ausgang bei einer Verbesserung des Zustandes wieder ausgedehnt werden soll.
3.3 Mit Ausnahme der Gewaltäusserungen, welche der Beschwerdeführer mit der Aussage, es bestehe keine Fremdgefährdung, da er sich grundsätzlich adäquat und freundlich verhalte, jedenfalls sinngemäss bestreitet, ohne jedoch im Zusammenhang mit der betreffenden Sachverhaltsfeststellung eine Verletzung verfassungsmässiger Rechte zu rügen, stellt er weder die tatsächlichen Feststellungen zu Art und Schwere seiner gesundheitlichen Beeinträchtigung noch die rechtliche Qualifikation dieses Zustandes - Vorliegen einer Geisteskrankheit - durch die Verwaltungsrekurskommission in Frage. Er ist jedoch der Meinung, dass er entweder in der betreuten Wohngemeinschaft "E._", die auch über geschützte Werkstätten verfüge, oder auf dem biologisch-dynamischen Landwirtschaftsbetrieb D._ leben könnte. Letztere Institution habe Platz und sei bereit, ihn für eine Probezeit aufzunehmen. Die Psychiatrische Klinik A._ gebe ihm aber keine Möglichkeit, diesen Betrieb kennenzulernen. Ganz generell seien weder die Klinikleitung noch sein Vormund je bereit gewesen, eine Platzierung ausserhalb des Anstaltsareals zu versuchen, dies mit dem unzutreffenden Hinweis, er würde innert kurzer Zeit völlig verwahrlosen. Damit werde jede Veränderung verunmöglicht und der Grundsatz der Verhältnismässigkeit des Eingriffes in die persönliche Freiheit, mithin <ref-law> und Art. 10 Abs. 1 i.V.m. <ref-law> verletzt.
3.4 Angesichts der unbestrittenen Geisteskrankheit liegt einer der in <ref-law> genannten Schwächezustände vor. Entgegen der Behauptung des Beschwerdeführers äussert sie sich unter anderem in brachialgewaltigem Verhalten, das insbesondere bei fehlender Medikamentation auftritt. Der Beschwerdeführer bedarf mithin der persönlichen Fürsorge durch Unterbringung und Pflege sowie geeignete Behandlung. Angesichts der fehlenden Realitätswahrnehmung sowohl mit Bezug auf seine Lebensumstände als auch auf andere Menschen sowie aufgrund seiner fehlenden Krankheitseinsicht kann die nötige Fürsorge nur stationär in einer geeigneten Anstalt erbracht werden.
Wie die Verwaltungsrekurskommission richtig festgehalten hat, geht die Meinung des Beschwerdeführers, er könnte auf dem Hof D._ - einer heilpädagogischen Institution mit integriertem Landwirtschaftsbetrieb und angegliedertem Wohnheim - leben, den er noch nie besichtigt hat und auf dem Jugendliche die Möglichkeit einer Anlehre in der Landwirtschaft haben, völlig an der Realität vorbei und kann es sich dabei auch nicht um die für den 70-jährigen Beschwerdeführer geeignete Anstalt handeln. Als Beispiel für den fehlenden Realitätsbezug und die fehlende Krankheitseinsicht seien sodann exemplarisch seine Ausführungen bei der mündlichen Einvernahme durch die Verwaltungsrekurskommission zum Vorfall mit dem elfjährigen Mädchen erwähnt: Er suche eben eine Frau. Er sei noch nicht zu alt. Dieses Mädchen hätte ihm allerdings nicht gepasst. Sie sei ausländisch und habe Schlitzaugen. Mit Jungfrauen könne er nichts anfangen. Das sei aber kein Kind mehr gewesen. Er sei ihr nicht nachgelaufen in die Papeterie. Er habe sie dort zufällig wieder getroffen. Das Mädchen habe nichts von ihm gewollt. Sie habe geweint, als er wieder gegangen sei. Als Matrose habe er massenhaft junge Mädchen gehabt. Das seien keine Huren gewesen, sondern Liebesdienerinnen. Mit elf Jahren sei dieses Mädchen nicht zu jung, falls es schon einen Mann gehabt habe. Er habe nicht auf die Brüste des Mädchens geschaut. Das mache er jeweils nur bei jenen Frauen, die wie Huren am Bahnhof ständen. Da bekomme er eine Erektion.
Kann dem Beschwerdeführer die infolge seiner Geisteskrankheit notwendige persönliche Fürsorge nur im Rahmen eines stationären Klinikaufenthaltes gewährt werden, erweist sich die Massnahme der FFE als notwendig und gleichzeitig auch als verhältnismässig. Die Psychiatrische Klinik A._ ist sodann offensichtlich die zur Behandlung der Krankheit geeignete Anstalt, weshalb der Beschwerdeführer dort zurückzubehalten ist.
4. Wie die voranstehenden Erwägungen zeigen, muss die Beschwerde als von Anfang an aussichtslos bezeichnet werden, weshalb es an den materiellen Voraussetzungen der unentgeltlichen Rechtspflege mangelt (<ref-law>). Mit Blick auf die finanzielle Situation des Beschwerdeführers wird jedoch auf die Erhebung von Gerichtskosten verzichtet.

Demnach erkennt das Bundesgericht:
1. Die Beschwerde in Zivilsachen wird abgewiesen, soweit darauf einzutreten ist.
2. Es werden keine Kosten erhoben.
3. Dieses Urteil wird dem Beschwerdeführer, der Psychiatrischen Klinik A._ und der Verwaltungsrekurskommission des Kantons St. Gallen, Abteilung V, schriftlich mitgeteilt.
Lausanne, 12. Mai 2010
Im Namen der II. zivilrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Die Präsidentin: Der Gerichtsschreiber:
Hohl Möckli