Sachverhalt:
A. A._ erstellte im Sommer 2000 für X._ auf dessen Liegenschaft in B._ (AR) eine Hangentwässerung. X._ erstattete am 24. Juli 2001 Strafklage gegen A._ wegen Betrugs. Er machte geltend, A._ habe Leistungen verrechnet, die er nicht erbracht habe. Das Strafverfahren wurde bis zum Abschluss des parallel laufenden Zivilprozesses zwischen den Beiden vorläufig eingestellt.
B. Das Verhöramt von Appenzell A.Rh. stellte das Strafverfahren mit Verfügung vom 29. Mai 2006 ein. Dagegen rekurrierte X._. Die Staatsanwaltschaft Appenzell A.Rh. schützte mit Entscheid vom 12. Juli 2006 den Rekurs und wies das Verhöramt an, das Strafverfahren wieder anzunehmen, bei X._ einen Kostenvorschuss einzuverlangen und nach dessen Eingang die notwendigen Untersuchungshandlungen durchzuführen. In der Folge verurteilte das Verhöramt A._ mit Strafverfügung vom 23. Februar 2007 wegen versuchten Betrugs. A._ und X._ erhoben beide Einsprache.
C. Der Einzelrichter des Kantonsgerichts sprach A._ mit Urteil vom 9. Juni 2009 von der Anklage des versuchten Betrugs frei und legte die Verfahrenskosten dem Staat auf. X._ und die Staatsanwaltschaft erhoben Appellation. Das Obergericht von Appenzell A.Rh. bestätigte mit Urteil vom 20. September 2010 den Freispruch. In Gutheissung der Appellation der Staatsanwaltschaft legte es X._ die Untersuchungskosten sowie die erst- und zweitinstanzlichen Gerichtskosten auf. Es verpflichtete ihn, A._ für dessen Anwaltskosten zu entschädigen.
D. Mit Beschwerde in Strafsachen beantragt X._, das Urteil des Obergerichts sei im Kosten- und Entschädigungspunkt aufzuheben. Die Verfahrenskosten und die Entschädigung an A._ seien vom Staat zu tragen. Die von ihm geleisteten Kostenvorschüsse seien ihm zurückzuerstatten.
E. Das Obergericht verzichtet auf Vernehmlassung, während die Staatsanwaltschaft die Abweisung der Beschwerde beantragt.

Erwägungen:
1. Die Vorinstanz sprach A._ in erster Linie von der Anklage des Betrugs frei, weil der Vorwurf, er habe den Entwässerungsgraben nicht so tief ausgehoben wie vertraglich abgemacht, zufolge nachträglicher Geländeveränderungen nicht mehr überprüft werden könne. In zweiter Linie sei das objektive Tatbestandsmerkmal der Arglist nicht erfüllt (angefochtenes Urteil E. 2.5 S. 17).
2. Der Beschwerdeführer rügt, die vorinstanzliche Kostenverlegung sei willkürlich und verstosse gegen Treu und Glauben.
2.1 Das angefochtene Urteil ist vor dem Inkrafttreten der Schweizerischen Strafprozessordnung vom 5. Oktober 2007 (Strafprozessordnung, StPO; SR 312.0) am 1. Januar 2011 ergangen. Die vorliegende Beschwerde ist deshalb nach bisherigem Recht zu beurteilen (<ref-law>).
Nach Art. 243 Abs. 1 Satz 1 des Gesetzes über den Strafprozess des Kantons Appenzell A.Rh. vom 30. April 1978 (StPO/AR, aufgehoben am 1. Januar 2011) können dem Geschädigten oder Anzeiger die Kosten ganz oder teilweise überbunden werden, wenn er das Verfahren erschwert oder durch verwerfliches oder unkorrektes Verhalten veranlasst hat. Wird eine Sicherheitsleistung nach Art. 145 verlangt, so haftet der Geschädigte ausserdem für die Kosten aller Untersuchungshandlungen, die er veranlasst hat, soweit sie erfolglos verlaufen, sowie für die Gerichtskosten im Falle eines Freispruchs (<ref-law>/AR). Unter der Voraussetzung von Art. 243 kann der Geschädigte oder Anzeiger ganz oder teilweise zur Bezahlung der Entschädigung und der Kosten der amtlichen Verteidigung verpflichtet werden (<ref-law>/AR).
Das Verhöramt kann den Geschädigten verpflichten, für die Untersuchungs- und Gerichtskosten eine Sicherheitsleistung zu erbringen. Wird sie nicht innerhalb der angesetzten Frist geleistet, so wird auf Grund der vorliegenden Akten entschieden (<ref-law>/AR).
2.2 Die Vorinstanz erwägt, sie habe in einem früheren Entscheid auf die im <ref-ruling> dargelegten Kostengrundsätze verwiesen. Danach könne bei Offizialdelikten der Geschädigte oder Strafkläger nur zur Kostenübernahme verpflichtet werden, wenn er das Verfahren veranlasst oder wesentlich erschwert habe. Im Grundsatz sei dem zuzustimmen. Indessen dürfe der eindeutige Wortlaut des Gesetzes nicht ausser Acht gelassen werden. Werde eine Sicherheitsleistung verlangt, so hafte der Geschädigte nach <ref-law>/AR im Falle eines Freispruchs ohne Einschränkungen für die Untersuchungs- und Gerichtskosten. Zudem seien die im konkreten Einzelfall in Frage stehenden Interessen und Umstände zu beachten. Der vorliegenden Streitigkeit zwischen dem Beschwerdeführer und A._ liege im Gegensatz zum <ref-ruling> ein Werkvertrag und somit eine zivilrechtliche Angelegenheit zugrunde. Die Auseinandersetzung sei zwar in zivilrechtlicher Hinsicht mit Urteil des Kantonsgerichts vom 23. August 2004 erledigt worden. Jedoch würden im Strafverfahren die privaten Interessen des Beschwerdeführers den Strafanspruch des Staates überwiegen. Verletztes Rechtsgut sei das Vertrauen in die mit dem Vertragspartner getroffenen Abmachungen, und es gehe insbesondere um die Feststellung der geltend gemachten (zivilrechtlichen) Nachteile. Weiter könne dem Beschwerdeführer zwar nicht vorgeworfen werden, dass er das Verfahren durch verwerfliches oder unkorrektes Verhalten veranlasst habe. Als Grundeigentümer habe er aber zu verantworten, dass aufgrund der nachträglichen Geländeveränderungen nicht mehr habe festgestellt werden können, wie tief der Graben ursprünglich ausgehoben worden sei. In diesem Sinne habe er das Verfahren ohne Not erschwert. Er hätte beispielsweise eine vorsorgliche Beweissicherung nach Art. 229 f. ZPO/AR veranlassen können. Letztlich falle ins Gewicht, dass der Beschwerdeführer die Verpflichtungen zur Leistung der Kostenvorschüsse nicht angefochten habe (angefochtenes Urteil E. 3.5 S. 21 ff.).
2.3 Der Beschwerdeführer bringt vor, gemäss der bisherigen Praxis der Vorinstanz zur Kostenverlegung löse die Sicherheitsleistung nach <ref-law>/AR keine vorbehaltlose Haftung des Geschädigten aus. Die Vorinstanz habe ihre langjährige Praxis ohne Vorankündigung zu seinem Nachteil geändert. Dies laufe dem Gerechtigkeitsgedanken in stossender Weise zuwider und verletze den Vertrauensgrundsatz. Im Vertrauen auf die bisherige Praxis habe er keine Veranlassung gehabt, die verfügte Sicherheitsleistung anzufechten. Dies gelte umso mehr, als er das Verfahren bei Verfügung der Sicherheitsleistung nicht durch weitere Rechtsmittel habe verzögern wollen. Soweit die Praxisänderung entgegen seiner Ansicht zulässig sei, basiere sie auf einer falschen Aktenlage und stelle eine willkürliche Rechtsanwendung dar. Die vorinstanzliche Behauptung, wonach die vorliegende Auseinandersetzung einen privaten Charakter habe, sei willkürlich. Betrugshandlungen basierten regelmässig auf vertraglichen Beziehungen, wobei verletztes Rechtsgut das Vertrauen des Geschädigten sei. Weil das zivilrechtliche Urteil rechtskräftig sei, habe er aus dem Strafverfahren keinerlei zivilrechtlichen Vorteile mehr erzielen können. Auch sei willkürlich, dass er die Beweislosigkeit zu verantworten habe. Er habe die Angelegenheit frühzeitig zur Anzeige gebracht und nicht verzögert.
2.4 <ref-law> gewährleistet jeder Person den Anspruch darauf, von den staatlichen Organen ohne Willkür und nach Treu und Glauben behandelt zu werden.
Behördliches Verhalten, das berechtigtes Vertrauen verletzt, verstösst unmittelbar gegen die Verfassungsgarantie (<ref-ruling> E. 1 S. 508 mit Hinweisen). Der verfassungsrechtliche Vertrauensschutz setzt ein Verhalten oder eine Äusserung der Behörde voraus, die gegenüber einer bestimmten Person eine Vertrauensgrundlage schafft. Nach der Rechtsprechung verleiht der Grundsatz von Treu und Glauben einer Person unter gewissen Voraussetzungen Anspruch auf Schutz des berechtigten Vertrauens in behördliche Zusicherungen oder sonstiges, bestimmte Erwartungen begründendes Verhalten der Behörden (<ref-ruling> E. 6.1 S. 636 mit Hinweisen).
Die vorinstanzliche Sachverhaltsfeststellung kann nur gerügt werden, wenn sie willkürlich (<ref-law>) ist oder auf einer Rechtsverletzung im Sinne von <ref-law> beruht und wenn die Behebung des Mangels für den Ausgang des Verfahrens entscheidend sein kann (<ref-law>; <ref-ruling> E. 1.4.1 S. 39 mit Hinweisen). Willkür liegt nach ständiger Rechtsprechung vor, wenn der Entscheid offensichtlich unhaltbar ist, mit der tatsächlichen Situation in klarem Widerspruch steht, eine Norm oder einen unumstrittenen Rechtsgrundsatz krass verletzt oder in stossender Weise dem Gerechtigkeitsgedanken zuwiderläuft (<ref-ruling> E. 1.3 S. 316; <ref-ruling> E. 4.2.1 S. 362; je mit Hinweisen).
2.5 Gemäss bundesgerichtlicher Rechtsprechung dürfen die Kosten der Erfüllung einer staatlichen Aufgabe nicht in untragbarer Weise auf Private abgewälzt werden. Bei Offizialdelikten lässt sich die Kostenauflage an den Verzeiger oder Privatkläger mit vernünftigen Gründen nur rechtfertigen, wenn sein Verhalten zu missbilligen ist, weil er die Einleitung des Verfahrens leichtfertig oder arglistig veranlasst oder dessen Durchführung erschwert hat (<ref-ruling> E. 3 S. 16; Urteil 1P.38/2002 vom 7. März 2002 E. 3.2).
Das Obergericht Appenzell A.Rh. hielt im Entscheid vom 23. Oktober 1984 unter Berufung auf <ref-ruling> fest, bei Offizialdelikten würden die gesamte Untersuchung, die Beweisführung und die Anklage dem Staat obliegen. Ihm stehe nicht nur der materielle Strafanspruch zu, sondern auch das Recht und die Pflicht, diesen durchzusetzen. Die Sicherheitsleistung habe nichts mit verwerflichem oder unkorrektem Veranlassen der Untersuchung oder mit deren Erschwerung zu tun. Deshalb lasse sich die Kostenpflicht des Geschädigten nicht schon aus der Tatsache der Bevorschussung nach <ref-law>/AR herleiten (Entscheid des Obergerichts Appenzell A.Rh. vom 23. Oktober 1984, in: Ausserrhodische Gerichts- und Verwaltungspraxis, AR GVP 1988 S. 462 f.).
2.6 Die Rüge der unzulässigen Praxisänderung bzw. der Verletzung des Vertrauensgrundsatzes ist unbegründet. Die Staatsanwaltschaft hielt im Anschluss an den Entscheid des Obergerichts vom 23. Oktober 1984 fest, unter dem Eindruck dieses Urteils sei bei Offizialdelikten hinsichtlich der Möglichkeit der Bevorschussung Zurückhaltung ausgeübt worden. Die Staatsanwaltschaft habe jedoch die Vorschusspflicht nicht grundsätzlich ausgeschlossen, sondern im Einzelfall die in Frage stehenden Interessen abgewogen und sich unter anderem am verletzten Rechtsgut und am Gewicht der privaten Vorteile, welche der Geschädigte mit seiner Beteiligung am Strafverfahren anstrebe, orientiert (Rekursentscheid der Staatsanwaltschaft vom 4. Oktober 1989, AR GVP 1989 Nr. 3153 S. 98; vgl. FELIX BÄNZIGER/AUGUST W. STOLZ/WALTER KOBLER, Kommentar zur Strafprozessordnung des Kantons Appenzell A.Rh., 2. Aufl. 1992, N. 4 zu Art. 145). Nach dem Gesagten ist eine gefestigte Praxis weder ersichtlich noch vom Beschwerdeführer dargetan. Zudem wurde der Beschwerdeführer in der Verfügung der Sicherheitsleistung auf die Konsequenzen des Kostenvorschusses aufmerksam gemacht. Gegen diese Verfügung reichte er keinen Rekurs ein (s. Verfügung des Verhöramts vom 29. Juli 2006, kantonale Akten pag. 33). Bei dieser Sachlage konnte er nicht in guten Treuen darauf vertrauen, trotz Leistung des Kostenvorschusses kein Kostenrisiko zu tragen.
2.7 Die Rüge, die Kostenauflage und Entschädigungsregelung basiere auf einer offensichtlich unrichtigen Feststellung des Sachverhalts und stelle eine willkürliche Rechtsanwendung dar, erweist sich hingegen als begründet. Die vorinstanzliche Feststellung, wonach es sich im vorliegenden Verfahren um eine vorwiegend zivilrechtlich geprägte Auseinandersetzung handle, ist offensichtlich unhaltbar. Die Streitigkeit zwischen dem Beschwerdeführer und A._ wurde in zivilrechtlicher Hinsicht mit Urteil des Kantonsgerichts von Appenzell A.Rh. vom 23. August 2004 abgeschlossen (s. kantonale Akten pag. 18). Die Vorinstanz legt weder dar noch ist ersichtlich, welche finanziellen Interessen der Beschwerdeführer im Strafverfahren verfolgen könnte. Zudem wendet der Beschwerdeführer zu Recht ein, dass der Tatbestand des Betrugs wie die meisten Delikte gegen Allgemeininteressen Vermögensinteressen (mit-)schützt (<ref-ruling> E. 4.3.3 S. 262 mit Hinweis). Unbestritten ist, dass der Beschwerdeführer das Verfahren nicht durch verwerfliches oder unkorrektes Verhalten veranlasst hat. Es ist nicht nachvollziehbar, inwiefern er das Verfahren ohne Not erschwert haben soll. Er erhob im Jahre 2001 Strafklage, wobei die anschliessende Untersuchung und Beweisführung dem Staat oblag. Somit trifft ihn kein prozessuales Verschulden an der Beweislosigkeit des Betrugs. Daran ändert auch der Umstand nichts, dass er im Zivilverfahren keine vorsorgliche Beweissicherung beantragte. Nach dem Gesagten hat der Beschwerdeführer keine Kosten zu tragen und ist demnach auch von der Pflicht zur Leistung einer Entschädigung an A._ befreit (<ref-law>/AR).
3. Die Beschwerde ist gutzuheissen, das angefochtene Urteil im Kosten- und Entschädigungspunkt aufzuheben und die Sache zur neuen Entscheidung an die Vorinstanz zurückzuweisen. Bei diesem Ausgang des Verfahrens sind keine Kosten zu erheben (Art. 66 Abs. 1 und 4 BGG) und hat der Kanton Appenzell Ausserrhoden dem Beschwerdeführer eine Entschädigung zu zahlen (<ref-law>).

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird gutgeheissen, die Ziffern 2 (Verfahrenskosten) und 3 (Entschädigung) des Urteils des Obergerichts von Appenzell Ausserrhoden vom 20. September 2010 aufgehoben und die Sache zu neuer Entscheidung an die Vorinstanz zurückgewiesen.
2. Es werden keine Kosten erhoben.
3. Der Kanton Appenzell Ausserrhoden hat dem Beschwerdeführer eine Parteientschädigung von Fr. 3'000.-- zu zahlen.
4. Dieses Urteil wird den Parteien und dem Obergericht von Appenzell Ausserrhoden, 1. Abteilung, schriftlich mitgeteilt.
Lausanne, 5. September 2011
Im Namen der Strafrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Mathys
Die Gerichtsschreiberin: Binz