A.- Mit Entscheid vom 22. November 1995 wies das Verwaltungsgericht von Appenzell A.Rh. die Beschwerde des K._ und einer weiteren Person gegen den Einspracheentscheid der Basler Versicherungs-Gesellschaft (nachfolgend: Basler) vom 4. November 1994 ab, womit diese eine Leistungspflicht im Zusammenhang mit seinem Verkehrsunfall vom 15. Oktober 1993 mangels Versicherteneigenschaft abgelehnt hatte.
Im August 1996 erstattete das Gericht u.a. gegen K._ Anzeige wegen Verdachts auf deliktischen Versuch der Erlangung von Unfallversicherungsleistungen. Das nach der Strafuntersuchung eingeleitete Strafverfahren endete am 24. Februar 1998 mit einem Freispruch durch das Obergericht des Kantons Appenzell A.Rh. Die Staatsanwaltschaft meldete hiegegen rechtzeitig eidgenössische Nichtigkeitsbeschwerde an, verzichtete aber schliesslich auf den Weiterzug der Sache, was dem Rechtsvertreter von K._ durch die Obergerichtskanzlei am 28. Mai 1998 mitgeteilt wurde.
Am 29. Juni 1998 ersuchte K._ die Basler um Wiederaufnahme des am 22. November 1995 (rechtskräftig) vor dem kantonalen Verwaltungsgericht abgeschlossenen Verfahrens. Mit Verfügung vom 9. November 1998 lehnte der Unfallversicherer das Begehren mit der Begründung ab, mit dem obergerichtlichen Strafurteil vom 24. Februar 1998 liege «keine gegenüber dem Tatbestand des ersten Entscheides wesentlich veränderte Sachlage» vor.
B.- Die von K._ hiegegen erhobene Beschwerde wies das Verwaltungsgericht von Appenzell A.Rh. mit Entscheid vom 29. September 1999 unter Kostenfolge ab.
C.- K._ lässt Verwaltungsgerichtsbeschwerde führen mit dem Rechtsbegehren, es seien Entscheid und Verfügung aufzuheben und das kantonale Gericht resp. die Basler «anzuweisen, die Unfallversicherungsansprüche (...) materiell zu behandeln».
Die Basler lässt Abweisung der Verwaltungsgerichtsbeschwerde beantragen. Das Bundesamt für Sozialversicherung hat sich nicht vernehmen lassen.

Das Eidg. Versicherungsgericht zieht in Erwägung:
1.- Es kann vorliegend offen bleiben, ob der Beschwerdeführer das Wiederaufnahmebegehren vom 29. Juni 1998, welches der Unfallversicherer als Gesuch um prozessuale Revision des Einspracheentscheides vom 4. November 1994 behandelte und ablehnte, rechtzeitig gestellt hat. Immerhin ist darauf hinzuweisen, dass sich diese Frage entgegen der Auffassung der Vorinstanz nicht nach kantonalem Recht, sondern nach Art. 67 VwVG beurteilte (RKUV 1994 Nr. U 191 S. 145). Davon abgesehen hätte der Unfallversicherer auf das Begehren nicht eintreten dürfen, nachdem die Beschwerdeinstanz über den zu revidierenden Einspracheentscheid rechtskräftig entschieden hatte. Denn dieser Verwaltungsakt war einerseits nie in Rechtskraft erwachsen, und anderseits ging mit der hiegegen formgültig erhobenen Beschwerde die Herrschaft über den Streitgegenstand auf die Rechtsmittelinstanz über, trat diese mit anderen Worten in jeder Beziehung an die Stelle des Unfallversicherers (nicht veröffentlichtes Urteil M. vom 15. März 1995 [U 14/95] zur gleichen Rechtslage im Verhältnis erst- und letztinstanzliches Verwaltungsgerichtsbeschwerdeverfahren in Unfallversicherungssachen).
2.- Der obergerichtliche Freispruch vom Vorwurf des strafbaren Versuchs, Unfallversicherungsleistungen auf betrügerische Weise zu erlangen, erging am 24. Februar 1998 (lange) nach dem unangefochten in Rechtskraft erwachsenen Beschwerdeentscheid vom 22. November 1995 und stellt daher keine revisionsbegründende neue Tatsache gemäss Art. 108 Abs. 1 lit. i UVG dar. Er kann aber entgegen den Vorbringen in der Verwaltungsgerichtsbeschwerde auch nicht als Beweismittel nach dieser Bestimmung gelten. Als solches hätte der Freispruch, und zwar im Sinne der Sachverhaltsermittlung und nicht bloss der Sachverhaltswürdigung, dem Beweis von Tatsachen zu dienen, die im erstinstanzlichen Beschwerdeverfahren bekannt gewesen, aber zum Nachteil des Gesuchstellers und heutigen Beschwerdeführers unbewiesen geblieben sind (vgl. <ref-ruling> Erw. 2, 108 V 171 f. Erw. 1; ferner <ref-ruling> Erw. 5). Dies ist hier klarerweise nicht der Fall. Selbst wenn aus dem strafrechtlichen Erkenntnis gefolgert werden könnte, dass entgegen der Annahme der Beschwerdeinstanz im Entscheid vom 22. November 1995 (mit überwiegender Wahrscheinlichkeit) «das behauptete Angestelltenverhältnis» nicht «zweckgerichtet fingiert wurde», kann darin lediglich eine abweichende Würdigung des gleichen Sachverhalts erblickt werden, was für eine Revision nicht genügt. Daran ändert nichts, dass das kantonale Gericht diesem Punkt seinerzeit entscheidende Bedeutung beigemessen hatte für die Frage der Arbeitnehmereigenschaft (vgl. Art. 1 UVG) und damit der Leistungspflicht des Unfallversicherers, zumal es nicht des Freispruchs von Schuld und Strafe in einem allfälligen späteren Strafverfahren bedurfte, um diese Annahme auf dem ordentlichen Rechtsmittelweg der Verwaltungsgerichtsbeschwerde anzufechten.
3.- Die Vorinstanz hat dem Beschwerdeführer Verfahrenskosten in der Höhe von Fr. 500.- auferlegt. Zur Begründung führt sie an, das Wiederaufnahmebegehren sei infolge der verpassten Frist von Anfang an aussichtslos gewesen, und durch die Beschwerde sei Aufwand verursacht worden. Es rechtfertige sich daher, von der Regel der Kostenlosigkeit des Verfahrens in Sozialversicherungssachen gemäss Art. 8 Abs. 1 des Gesetzes über die Verwaltungsgerichtsbarkeit und Art. 9 Abs. 2 lit. c des Gesetzes über die Gebühren in Verwaltungssachen abzuweichen.
Die Kostenauflage und deren Begründung muss als willkürlich bezeichnet werden. Zum einen lässt sich in der Tat fragen, ob, wie in der Verwaltungsgerichtsbeschwerde u.a. unter Hinweis auf <ref-ruling> f. Erw. 4a geltend gemacht wird, die Frist zur Stellung eines Revisionsgesuchs nicht erst mit Kenntnis vom Verzicht der Staatsanwaltschaft auf die beim Obergericht rechtzeitig angemeldete eidgenössische Nichtigkeitsbeschwerde (vgl. Art. 272 Abs. 1 BStP), somit erst am 28. Mai 1998 zu laufen begonnen hatte. Denn frühestens in diesem Zeitpunkt musste der Beschwerdeführer nicht mehr mit der Aufhebung des Freispruchs rechnen. Es kann somit keinesfalls gesagt werden, das Wiederaufnahmebegehren sei, da klar verspätet, aussichtslos gewesen. Die Vorinstanz führt sodann keine kantonalrechtliche Bestimmung für ihr Abweichen vom Grundsatz der Kostenlosigkeit des Verfahrens in Sozialversicherungssachen an. Auch im Bundessozialversicherungsrecht, dessen Anwendbarkeit auf das Revisionsverfahren nach Art. 108 Abs. 1 lit. i UVG offen bleiben kann (vgl. <ref-ruling> für das Verfahren gemäss Art. 85 Abs. 2 lit. h AHVG), liesse sich hiefür keine Grundlage finden. Insbesondere kann in Bezug auf die Frage der Rechtzeitigkeit des Gesuchs nicht von mutwilliger oder leichtsinniger Prozessführung gesprochen werden (vgl. <ref-ruling> in Verbindung mit <ref-ruling> f. Erw. 3b). Im Übrigen liesse sich auch fragen, ob die Vorinstanz unter Hinweis auf eine mögliche Kostenauferlegung dem Beschwerdeführer nicht hätte Gelegenheit zum Rückzug des Rechtsmittels geben müssen, wenn und soweit sie diese mit der Nichtrechtzeitigkeit des Wiederaufnahmebegehrens begründen wollte. Immerhin durfte er von der grundsätzlichen Kostenlosigkeit des erstinstanzlichen Verfahrens ausgehen und war der Unfallversicherer auf das Gesuch eingetreten, ohne sich zu den darin gemachten Ausführungen zur Rechtzeitigkeit zu äussern, hatte dieses materiell behandelt und in der Rechtsmittelbelehrung die Beschwerde an das kantonale Verwaltungsgericht genannt (vgl. <ref-ruling> vor Erw. 1b). Im Lichte der vorstehenden Ausführungen muss die Kostenauflage als rechtswidrig bezeichnet werden und ist daher aufzuheben.
4.- Das Verfahren vor dem Eidgenössischen Versicherungsgericht ist kostenpflichtig (Art. 134 OG e contrario; vgl. <ref-ruling> Erw. 5). Dem Prozessausgang entsprechend sind die Gerichtskosten zu 4/5 dem Beschwerdeführer und zu 1/5 der Basler aufzuerlegen (Art. 156 Abs. 3 in Verbindung mit Art. 135 OG).
Dem Beschwerdeführer steht nach Massgabe seines teilweisen Obsiegens eine reduzierte Parteientschädigung zu (Art. 159 Abs. 1 und 3 OG).

Demnach erkennt das Eidg. Versicherungsgericht:
I. In teilweiser Gutheissung der Verwaltungsgerichts-
beschwerde wird der Entscheid des Verwaltungsgerichts
von Appenzell A.Rh. vom 29. September 1999 im Kosten-
punkt aufgehoben. Im Übrigen wird die Verwaltungs-
gerichtsbeschwerde abgewiesen.
II. Die Gerichtskosten von Fr. 500.- werden zu 4/5 dem
Beschwerdeführer und zu 1/5 der Basler Versicherungs-
Gesellschaft auferlegt. Der auf den Beschwerdeführer
entfallende Anteil ist durch den geleisteten Kosten-
vorschuss von Fr. 500.- gedeckt; der Differenzbetrag
von Fr. 100.- wird ihm rückerstattet.
III. Die Basler Versicherungs-Gesellschaft hat dem Be-
schwerdeführer für das Verfahren vor dem Eidgenössi-
schen Versicherungsgericht eine Parteientschädigung
von Fr. 500.- zu bezahlen.
IV. Dieses Urteil wird den Parteien, dem Verwaltungs-
gericht von Appenzell A.Rh. und dem Bundesamt für
Sozialversicherung zugestellt.
Luzern, 11. Mai 2000
Im Namen des
Eidgenössischen Versicherungsgerichts
Der Präsident Der Gerichts der IV. Kammer: schreiber: