Sachverhalt:
A. Das Statthalteramt Arlesheim verurteilte X._ auf Anzeige seiner geschiedenen Ehefrau A._ hin mit Strafbefehl vom 4. Mai 2009 wegen Vernachlässigung von Unterhaltspflichten zu einer Geldstrafe von 90 Tagessätzen zu Fr. 160.--, bedingt aufgeschoben bei einer Probezeit von zwei Jahren, sowie zu einer Busse von Fr. 1'500.--. Es auferlegte ihm die Verfahrenskosten und verpflichtete ihn zur Bezahlung einer Parteientschädigung an die Anzeigestellerin.
X._ erhob gegen diesen Strafbefehl Einsprache, worauf ihn das Strafgerichtspräsidium Basel-Landschaft am 23. April 2010 in teilweiser Abänderung des Strafbefehls der mehrfachen Vernachlässigung von Unterhaltspflichten schuldig sprach und ihn zu einer Geldstrafe von 20 Tagessätzen zu Fr. 50.--, bedingt aufgeschoben bei einer Probezeit von zwei Jahren, sowie zu den hälftigen Verfahrenskosten und einer Parteientschädigung an die Anzeigestellerin verurteilte. Vom Vorwurf der Vernachlässigung von Unterhaltspflichten für die Monate August 2004, Juli 2007 und September 2007 sprach es ihn frei. Für den Zeitraum von Oktober 2001 bis Juli 2004 gab es dem Verfahren mangels gültigen Strafantrags keine Folge.
B. Das Kantonsgericht Basel-Landschaft hiess die von X._ hiergegen erhobene Appellation teilweise gut und sprach ihn in Bestätigung des angefochtenen Urteils der mehrfachen Vernachlässigung von Unterhaltspflichten schuldig, wobei es in Anwendung von <ref-law> von einer Bestrafung absah.
C. X._ führt Beschwerde in Strafsachen beim Bundesgericht. Er beantragt, das Urteil des Kantonsgerichts Basel-Landschaft vom 16. November 2010 sei aufzuheben, und das Strafverfahren gegen ihn sei definitiv einzustellen. Eventualiter sei er von jeglicher Schuld freizusprechen. Zudem sei er von den Gerichts- und Verfahrenskosten der kantonalen Instanzen sowie der Schadenersatzforderung gegen seine geschiedene Ehefrau A._ zu befreien. Die Sache sei zur Festsetzung der Parteientschädigung für beide kantonalen Verfahren an das Kantonsgericht Basel-Landschaft zurückzuweisen. Schliesslich sei ihm für das bundesgerichtliche Verfahren eine angemessene Parteientschädigung zulasten des Kantons Basel-Landschaft zuzusprechen.
D. Die Staatsanwaltschaft des Kantons Basel-Landschaft verzichtet auf eine Vernehmlassung. Das Kantonsgericht Basel-Landschaft sowie A._ beantragen die Abweisung der Beschwerde.

Erwägungen:
1. Gemäss <ref-law> ist zur Beschwerde in Strafsachen berechtigt, wer vor der Vorinstanz am Verfahren teilgenommen oder keine Möglichkeit zur Teilnahme erhalten (lit. a) und ein rechtlich geschütztes Interesse an der Aufhebung oder Änderung des angefochtenen Entscheids hat (lit. b). Hierunter fällt gemäss lit. b Ziff. 1 die beschuldigte Person. Die Vorinstanz hat den erstinstanzlichen Schuldspruch gegen den Beschwerdeführer bestätigt, hat in Anwendung von <ref-law> aber von einer Verurteilung abgesehen. Wie der Beschwerdeführer zu Recht festhält (Beschwerde, S. 3), ändert dies nichts daran, dass er durch das angefochtene Urteil beschwert ist. Dies ist im Übrigen auch aufgrund der ihm auferlegten Verfahrenskosten der Fall.
2. Die Vorinstanz geht von folgendem Sachverhalt aus:
Die Ehe zwischen dem Beschwerdeführer und der Beschwerdegegnerin 2 wurde am 13. Oktober 1997 geschieden. Im Rahmen der vom Bezirksgericht Arlesheim genehmigten Vereinbarung über die Nebenfolgen der Ehescheidung verpflichtete sich der Beschwerdeführer, ihr einen monatlichen Unterhaltsbeitrag von Fr. 1'200.-- zu zahlen. Grundlage bildeten die Netto-Einkommen des Beschwerdeführers und der Beschwerdegegnerin 2 von Fr. 53'379.50 bzw. Fr. 9'600.--. Der Unterhaltsbeitrag war an den BIGA-Landesindex der Konsumentenpreise sowie an die Einkommensveränderung des Beschwerdeführers gekoppelt, wobei ihm die Beweislast für eine geringere Einkommensanpassung oblag. Der Beschwerdeführer erzielte in den Jahren 2003 bis 2006 weniger Einkommen als 1996, zahlte jedoch gleichwohl den an die Teuerung angepassten, und damit zu hohen, Unterhaltsbeitrag. Er bezahlte die Unterhaltsbeiträge allerdings wiederholt verspätet. Der Rückstand betrug manchmal wenige Tage, zuweilen auch mehrere Monate. Die Beschwerdegegnerin 2 reichte deswegen verschiedene Strafanträge ein.
3.1 3.1.1 Der Beschwerdeführer macht geltend, er habe seiner geschiedenen Ehefrau aus Irrtum jahrelang zu hohe Unterhaltsbeiträge entrichtet. Diese Mehrleistungen habe er weder "à fonds perdu" noch schenkungsweise erbracht, sie seien vielmehr als Vorauszahlungen an die noch nicht fälligen Geldleistungen zu qualifizieren. So habe sich mit der Zeit ein beträchtlicher Mehrbetrag von mehreren Tausend Franken bilden können. Aufgrund seiner teilweisen verspäteten Zahlungen habe sich für die Monate August bis Oktober 2005 sowie Dezember 2005 ein Minussaldo ergeben. Dieser sei durch eine per 24. Januar 2006 erfolgte Ausgleichszahlung von Fr. 5'012.-- aufgehoben und in einen Mehrbetrag umgewandelt worden. Auch vom 12. April 2006 bis 4. Oktober 2006 habe er keine Unterhaltszahlungen geleistet. Anfang Oktober 2006 habe daher ein Minussaldo resultiert, den er am 5. Oktober 2006 durch Zahlung von Fr. 9'500.-- nicht nur ausgeglichen, sondern in einen Positivsaldo überführt habe. Seither habe ihm zu keinem Zeitpunkt ein Minussaldo zur Last gelegt werden können. Die überschiessenden Mehrbeträge habe er sich auf seine später fälligen Unterhaltszahlungen anrechnen lassen dürfen (Beschwerde, S. 5).
3.1.2 Weiter führt der Beschwerdeführer aus, die Beschwerdegegnerin 2 habe nur bis am 24. April 2006 für den per 23. Januar 2006 resultierenden Ausstand und für den am 5. Oktober 2006 ausgeglichenen Minussaldo bis am 8. Januar 2007 Strafantrag erheben können. Ihre Strafanträge vom 11. April 2007, 4. Juni 2007 und 14. September 2007 seien entgegen der Vorinstanz verspätet. Ihre Berücksichtigung verletze Art. 31 und <ref-law> (Beschwerde, S. 6 f.).
3.1.3 Nach Auffassung des Beschwerdeführers nimmt die Vorinstanz aus nicht nachvollziehbaren Gründen an, die zu hohen Unterhaltszahlungen seien nicht als Guthaben für die später fällig gewordenen Unterhaltsbeiträge zu qualifizieren. Die Vorinstanz verletze <ref-law>, wonach die Verrechnung ohne weiteres Rückwirkung entfalte. Zudem habe er die Verrechnungseinrede nicht nur gegenüber der Beschwerdegegnerin 2, sondern auch im Ermittlungsverfahren vor der ersten Einvernahme erhoben. Die Vorinstanz hätte daher die Verrechnungseinrede berücksichtigen müssen. Eine zeitliche Limitierung zur Geltendmachung der zuviel bezahlten Unterhaltsbeiträge ergebe sich aus dem Scheidungsurteil im Übrigen nicht (Beschwerde, S. 6 f.).
3.1.4 Schliesslich rügt der Beschwerdeführer, die Vorinstanz verletze Bundesrecht, indem sie das Verfahren nicht eingestellt habe, sondern ihn lediglich als "Trostpflaster" gemäss <ref-law> von einer Strafe befreie. Eine Wiedergutmachung sei nicht erst im Gerichtsverfahren, sondern bereits vor der ersten Einvernahme im Untersuchungsverfahren erfolgt (Beschwerde, S. 7).
3.1.4 Schliesslich rügt der Beschwerdeführer, die Vorinstanz verletze Bundesrecht, indem sie das Verfahren nicht eingestellt habe, sondern ihn lediglich als "Trostpflaster" gemäss <ref-law> von einer Strafe befreie. Eine Wiedergutmachung sei nicht erst im Gerichtsverfahren, sondern bereits vor der ersten Einvernahme im Untersuchungsverfahren erfolgt (Beschwerde, S. 7).
3.2 3.2.1 Die Vorinstanz erwägt, die Vernachlässigung von Unterhaltspflichten stelle ein Dauerdelikt dar, weshalb die Strafantragsfrist erst mit der letzten verschuldeten Unterlassung zu laufen beginne.
Der Beschwerdeführer habe seit Januar 2001 zu hohe Unterhaltsbeiträge bezahlt. Es habe ihm aber gemäss Scheidungsurteil der Nachweis oblegen, dass sich sein Einkommen nicht der Teuerung angepasst habe. Da er dieser Verpflichtung nicht nachgekommen sei, habe die Beschwerdegegnerin 2 davon ausgehen können, es sei ein teuerungsangepasster Unterhaltsbeitrag geschuldet. Der Beschwerdeführer habe selber diese Auffassung vertreten. Diese aus heutiger Sicht zu hohen Unterhaltsbeiträge könnten nicht automatisch als Guthaben für die später fällig gewordenen qualifiziert werden. Hierfür hätte er explizit die Verrechnung erklären müssen, zumal Unterhaltsansprüche nicht gegen den Willen des Gläubigers durch Verrechnung getilgt werden dürften (angefochtenes Urteil, S. 5 ff.).
3.2.2 Die Vorinstanz führt weiter aus, die Unterhaltsbeiträge seien im Zeitraum von September 2004 bis April 2007 nicht rechtzeitig oder nicht vollständig bezahlt worden. Der Strafantrag vom 11. April 2007 sei daher rechtzeitig gestellt worden. Im Mai und Juni 2007 sowie im August 2007 seien die Unterhaltsbeiträge auch verspätet beglichen worden, weshalb die Strafanträge vom 4. Juni 2007 und 14. September 2007 ebenfalls rechtzeitig erhoben worden seien (angefochtenes Urteil, S. 7).
3.2.3 Nach Auffassung der Vorinstanz ist der objektive Tatbestand von <ref-law> erfüllt, weil der Beschwerdeführer im inkriminierten Zeitraum die Unterhaltsbeiträge verspätet geleistet habe, obschon er über die erforderlichen Mittel verfügt habe, rechtzeitig zu leisten. Subjektiv sei der Tatbestand ebenfalls erfüllt, da der Beschwerdeführer um seine Leistungspflicht per Ende des jeweiligen Vormonats gewusst habe. Dass er mit der Nichtleistung der Beiträge während mehrerer Monate die Beschwerdegegnerin 2 habe dazu bringen wollen, die Tagebücher ihres verstorbenen Sohnes herauszugeben, sei zwar menschlich nachvollziehbar, ändere an der Rechtswidrigkeit seines Vorgehens aber nichts (angefochtenes Urteil, S. 7 f.).
3.3 Gemäss <ref-law> wird auf Antrag mit Freiheitsstrafe bis zu drei Jahren oder Geldstrafe bestraft, wer seine familienrechtlichen Unterhalts- oder Unterstützungspflichten nicht erfüllt, obschon er über die Mittel dazu verfügt oder verfügen könnte.
Die Tathandlung besteht im Unterlassen, bei Fälligkeit die geschuldete Leistung zu erbringen. Das Antragsrecht erlischt nach Ablauf von drei Monaten (<ref-law>). Die Antragsfrist beginnt, sobald dem Antragsberechtigten Täter und Tat, d.h. deren Tatbestandselemente, bekannt sind. Erforderlich ist dabei eine sichere, zuverlässige Kenntnis, die ein Vorgehen gegen den Täter als aussichtsreich erscheinen lässt. Wenn der Pflichtige während einer gewissen Zeit ohne Unterbrechung schuldhaft die Zahlung der Unterhaltsbeiträge unterlässt, beginnt nach der Rechtsprechung die Antragsfrist erst mit der letzten schuldhaften Unterlassung zu laufen (<ref-ruling> E. 3.1). Der Antrag ist gültig für den Zeitraum, in dem der Täter ohne Unterbrechung den Tatbestand erfüllt hat. Der Strafantragsberechtigte darf daher mit der Stellung des Strafantrages - auch wenn er ihn schon vor Beginn des Fristenlaufs stellen kann - solange unbeschadet zuwarten, als der Unterhaltspflichtige schuldhaft die geschuldeten Beiträge nicht bezahlt. Bei mehreren monatlich geschuldeten Unterhaltsbeiträgen, die während einer bestimmten Zeitspanne nicht geleistet wurden, beginnt daher die Strafantragsfrist beispielsweise erst, wenn der Pflichtige wieder mit Zahlungen beginnt, oder wenn er mangels Leistungsfähigkeit seiner Zahlungspflicht nicht nachkommen kann (<ref-ruling> E. 2a mit Hinweisen).
3.4 Zu prüfen ist, ob der Beschwerdeführer seiner Unterhaltspflicht fristgerecht nachgekommen ist. Falls dies nicht der Fall ist, stellt sich die weitere Frage, ob die Beschwerdegegnerin 2 rechtzeitig Strafantrag gestellt hat. Gemäss Vereinbarung über die Nebenfolgen der Ehescheidung zwischen dem Beschwerdeführer und der Beschwerdegegnerin 2 verpflichtete sich dieser (unter Vorbehalt der eingangs erwähnten Indexierung) "einen monatlichen und vorauszahlbaren Unterhaltsbeitrag von Fr. 1'200.-- (...) zu bezahlen".
Entgegen den Ausführungen der Vorinstanz beschlagen die Zahlungen des Beschwerdeführers nicht das Institut der Verrechnung (<ref-law>), sondern die Frage der Anrechnung von Teilzahlungen an bestehende Schulden (<ref-law>), zumal sich nicht zwei Forderungen zweier verschiedener Personen gegenüberstehen. Leistungspflichtig ist lediglich der Beschwerdeführer.
3.5 Die Vereinbarung über die Nebenfolgen der Ehescheidung legt keine genauen Zahlungsmodalitäten fest, sondern spricht - wie erwähnt - lediglich von einem "monatlichen und vorauszahlbaren Unterhaltsbeitrag", womit eine Zahlung im Vormonat für den jeweiligen Folgemonat gemeint ist. Eine frühere Zahlung wird dadurch allerdings nicht ausgeschlossen. Liegt weder eine gültige Erklärung über die Tilgung noch eine Bezeichnung in der Quittung vor, ist nach <ref-law> die Zahlung auf die fällige Schuld anzurechnen, unter mehreren fälligen auf diejenige Schuld, für die der Schuldner zuerst betrieben worden ist, und hat keine Betreibung stattgefunden, auf die früher verfallene (Abs. 1). Sind sie gleichzeitig verfallen, so findet eine verhältnismässige Anrechnung statt (Abs. 2). Ist keine der mehreren Schulden verfallen, so wird die Zahlung auf die Schuld angerechnet, die dem Gläubiger am wenigsten Sicherheit darbietet (Abs. 3). Auf den vorliegenden Fall angewendet, sind die geleisteten Mehrbeträge des Beschwerdeführers somit auf die nächst fällige Unterhaltszahlung anzurechnen.
3.6 Der Beschwerdeführer beglich den geschuldeten Unterhaltsbeitrag für den Monat August 2004 pünktlich. Bis Juli 2005 bezahlte er jeweils einige Tage zu spät; im August, September und Oktober 2005 entrichtete er keine Unterhaltsbeiträge. Am 10. November 2005 leistete er für den Monat November 2005, im Dezember 2005 bezahlte er wiederum keinen Beitrag. Am 24. Januar 2006 entrichtete er Fr. 5'012.-- (4 x Fr. 1253.--) und beglich damit die ausstehenden Beiträge der Monate August, September, Oktober und Dezember 2005. Weitere Zahlungen von je Fr. 1'293.-- erfolgten am 7. Februar, 1. März und 11. April 2006, die auf die Monate Januar-März 2006 anzurechnen sind. Für die Monate April 2006 bis Oktober 2006 erfolgten wiederum keine Zahlungen. Am 5. Oktober 2006 leistete er Unterhaltsbeiträge im Umfang von Fr. 9'500.--. Er deckte damit die ausstehenden Beiträge von April 2006 bis Oktober 2006 ab (7 x Fr. 1'293.-- = Fr. 9'051.--), anderseits entrichtete er einen Mehrbetrag von Fr. 449.--, der gemäss <ref-law> auf den Folgemonat November 2006 anzurechnen war. Dieser Überschuss reichte jedoch nicht aus, den Zahlungsrückstand des Beschwerdeführers auszugleichen, da er in den Folgemonaten November 2006-Januar 2007 die Beiträge erneut um jeweils einige Tage zu spät bezahlte. Erst am 31. Januar 2007 erfolgte wieder eine pünktliche Überweisung für den Februar 2007, allerdings lediglich im Umfang von Fr. 900.-- statt Fr. 1'293.--. Unter Berücksichtigung des bestehenden positiven Saldos von Fr. 449.-- befand sich der Beschwerdeführer zu diesem Zeitpunkt jedoch nicht mehr im Zahlungsrückstand (für die einzelnen Zahlungen vgl. die Bankauszüge der Beschwerdegegnerin 2, pag. 147 ff., sowie die Zusammenstellung der geleisteten Zahlungen im erstinstanzlichen Urteil, S. 7, pag. 919 und 921 der Vorakten).
3.7 Der Beschwerdeführer hatte somit die geschuldeten Unterhaltsbeiträge zwischen August 2004 und Februar 2007 vollständig, jedoch immer verspätet beglichen. Da er gemäss Vorinstanz über die erforderlichen finanziellen Mittel verfügt hat, rechtzeitig zu leisten, erfüllt er den objektiven Tatbestand der Vernachlässigung von Unterhaltspflichten gemäss <ref-law>. Dass er um seine Leistungspflicht gewusst hat, ist unbestritten, weshalb die Vorinstanz zu Recht auch den subjektiven Tatbestand bejaht hat.
Die Strafantragsfrist gemäss <ref-law> von drei Monaten für die vor dem 31. Januar 2007 jeweils zu spät erfolgten Zahlungen begann am 1. Februar 2007 zu laufen und endete am 1. Mai 2007. Der Strafantrag vom 11. April 2007 erfolgte daher rechtzeitig. Da der Beschwerdeführer in den Folgemonaten seinen Unterhaltspflichten wiederum um jeweils einige Tage zu spät nachkam, erweisen sich auch die Strafanträge vom 4. Juni 2007 und 14. September 2007 als rechtzeitig. Die Verurteilung des Beschwerdeführers wegen Vernachlässigung von Unterhaltspflichten verletzt daher kein Bundesrecht.
3.8 An diesem Ergebnis kann die Argumentation des Beschwerdeführers nichts ändern, dass er wegen seines geringeren Einkommens in den Jahren nach dem Scheidungsurteil über einen längeren Zeitraum zu hohe Unterhaltsbeiträge bezahlt habe. Gemäss der damaligen Vereinbarung vom 13. Oktober 1997 trägt er die Beweislast für eine gegenüber der Teuerung geringere Einkommensanpassung (pag. 41 der Vorakten). Es ist unbestritten, dass der Beschwerdeführer nie ein entsprechendes Abänderungsbegehren gestellt hat, weshalb seine Unterhaltspflicht unverändert weiter bestand. Über ein allfälliges Abänderungsbegehren oder die Rückzahlung zuviel bezahlter Beiträge hat der Strafrichter nicht zu befinden.
4. 4.1 Der Beschwerdeführer wendet sich gegen die von der Vorinstanz bestätigte Zivilforderung zugunsten seiner geschiedenen Ehefrau. Es gehe nicht an, dass die Beschwerdegegnerin 2 ihre Strafanträge zu spät stelle, aufgrund seiner Mehrleistungen bereichert sei und gleichzeitig ihre Anwaltskosten im Sinne von Schadenersatz ersetzt haben wolle (Beschwerde, S. 8). Die Vorinstanz erwägt, die Zivilforderung sei vom Beschwerdeführer nicht angefochten worden, weshalb diese ohne weiteres zu bestätigen sei (angefochtenes Urteil, S. 9).
4.2 Dem Beschwerdeführer ist zuzustimmen, dass er im Rahmen seiner Appellation das gesamte erstinstanzliche Urteil - und damit einschliesslich der Zivilforderung - angefochten hat. Nach § 178 Abs. 3 aStPO/BL kann die schriftliche Appellationserklärung entweder nur die Appellation enthalten, so dass angenommen wird, die appellierende Person halte an dem in der Hauptverhandlung des Strafgerichts eingenommenen Standpunkt fest, oder sie kann auch Anträge und eine kurze Begründung aufweisen. Da der Beschwerdeführer erstinstanzlich einen "kostenlosen Freispruch" verlangte (pag. 901 der Vorakten), war sein Standpunkt hinreichend klar. Die Vorinstanz hätte daher über die Zivilforderung, welche die Anwaltskosten der Beschwerdegegnerin 2 umfasst, befinden müssen.
Von einer Aufhebung des vorinstanzlichen Urteils ist gleichwohl abzusehen. Der Beschwerdeführer stellt die Zivilforderung, wie schon vor den kantonalen Instanzen, lediglich grundsätzlich in Frage, indem er - zu Unrecht - eine Vernachlässigung von Unterhaltspflichten verneint. Da die Beschwerde in der Sache abzuweisen ist und der Beschwerdeführer die erstinstanzlich festgesetzten Anwaltskosten der Beschwerdegegnerin 2 betragsmässig nicht beanstandet, erübrigt sich eine Neubeurteilung durch die Vorinstanz, zumal nicht ersichtlich ist, inwiefern die Höhe der Zivilforderung Bundesrecht verletzt.
Nicht zu beanstanden ist schliesslich die vom Beschwerdeführer gerügte Kostenverteilung der Vorinstanz. Diese hat den erstinstanzlichen Schuldspruch bestätigt und lediglich von einer Bestrafung Umgang genommen, weshalb sie an der ursprünglichen Kostenverteilung festhalten durfte.
5. Die Beschwerde ist abzuweisen. Bei diesem Ausgang des Verfahrens sind dem Beschwerdeführer die Verfahrenskosten aufzuerlegen (<ref-law>). Dem Kanton Basel-Landschaft sind keine Gerichtskosten aufzuerlegen (Art. 66 Abs. 1 i.V.m. Abs. 4 BGG). Der Beschwerdeführer hat die Beschwerdegegnerin 2 für deren Kosten zu entschädigen (<ref-law>).

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird abgewiesen.
2. Die Gerichtskosten von Fr. 2'000.-- werden dem Beschwerdeführer auferlegt.
3. Der Beschwerdeführer hat die Beschwerdegegnerin 2 mit Fr. 2'000.-- zu entschädigen.
4. Dieses Urteil wird den Parteien und dem Kantonsgericht Basel-Landschaft, Abteilung Zivil- und Strafrecht, schriftlich mitgeteilt.
Lausanne, 19. Juli 2011
Im Namen der Strafrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Der Gerichtsschreiber:
Mathys Keller