Sachverhalt: A. Die Eheleute V._ und W._ reichten am 31. März 2009 ein Baugesuch betreffend die Parzelle Nr. 454 an der Rahmensbüelstrasse 40 in Schindellegi, Gemeinde Feusisberg, ein. Dieses umfasste den Abbruch des bestehenden Gebäudes und den Neubau eines Einfamilienhauses. Das Baugesuch wurde im Amtsblatt vom 9. April 2009 publiziert. Der Gemeinderat Feusisberg wies die dagegen erhobenen Einsprachen mit Beschluss vom 27. August 2009 ab, soweit er darauf eintrat, und erteilte die Baubewilligung. Während der Bauphase erhoben die Eheleute X._ und Y._, die sich am bisherigen Verfahren nicht beteiligt hatten, eine nachträgliche Einsprache. Diese wurde vom Gemeinderat Feusisberg mit Entscheid vom 1. Juni 2010 abgewiesen. Eine gegen den Entscheid des Gemeinderats eingelegte Verwaltungsbeschwerde wies der Regierungsrat des Kantons Schwyz mit Beschluss vom 22. März 2011 ab. In der Folge gelangten die Eheleute X._ und Y._ mit Beschwerde an das Verwaltungsgericht des Kantons Schwyz. Dieses wies ihr Rechtsmittel mit Entscheid vom 21. September 2011 ebenfalls ab. B. Mit einer als "Verfassungsbeschwerde" bezeichneten Eingabe an das Bundesgericht vom 7. November 2011 beantragen die Eheleute X._ und Y._, die vorinstanzlichen Entscheide seien aufzuheben und der Gemeinderat sei anzuweisen, die nachträgliche Baueinsprache zu behandeln und ein nachträgliches Baubewilligungsverfahren durchzuführen. Eventualiter sei die Angelegenheit an das Verwaltungsgericht zurückzuweisen. Das Verwaltungsgericht und die Beschwerdegegner beantragen die Abweisung der Beschwerde, soweit darauf einzutreten sei. Der Regierungsrat beantragt, auf die Beschwerde sei nicht einzutreten, eventualiter, sie sei abzuweisen. Der Gemeinderat Feusisberg hat auf eine Vernehmlassung verzichtet. Die Beschwerdeführer halten in ihrer Stellungnahme dazu im Wesentlichen an ihren Anträgen und Rechtsauffassungen fest. Während der Regierungsrat auf eine weitere Vernehmlassung verzichtete, nahmen das Verwaltungsgericht und der Gemeinderat Feusisberg zur Replik der Beschwerdeführer Stellung. Der Gemeinderat beantragte dabei die Abweisung der Beschwerde. Mit Schreiben vom 30. April 2012 informieren die Beschwerdeführer darüber, dass sie ihre Liegenschaft am 16. April 2012 verkauft haben. Die Beschwerdegegner äussern in einer weiteren Eingabe die Ansicht, dass aufgrund dieses Verkaufs die Legitimation der Beschwerdeführer wegfalle und deshalb auf die Beschwerde nicht einzutreten sei.