Das mit der Fernwartung würde ich erstmal ausschließen. Du öffnest in dem Fall die Box für jeden Angreifer, auch wenn man Userlogin und PW eingeben muss, wäre ich da sehr vorsichtig.
Primär solltest du erst mal dafür sorgen, dass im internen Netzwerk WOL geht. Danach kannst du dir Gedanken darüber machen, ob die die Oberfläche der FB nutzt oder das UDP-Paket als Broadcast ins LAN leitest.
Da du schreibst, dass die Fritzbox auch Magic-Pakete verschicken kann, dann versuche es doch mal damit. Als Referenz kannst du auch mal versuchen deinen Desktop-PC aufzuwecken. Man kann von ausgehen, dass jede aktuelle Hardware WOL unterstützt. Dann weißt du wenigstens schon mal, ob die FritzBox das Paket auch wirklich verwendet. Alternativ könntest du auch tcpdump laufen lassen. Das Tool gibt es auch für Windows.
Wenn du den Server ohne Umweg von deinem Desktop-System aus aufwecken willst, musst du bei Win7 die Firewalleinstellungen bearbeiten. Wie bereits geschrieben, hatte ich genau das Problem unter Win7. Nach dem deaktivieren der Firewall kommt das Paket auch durch und der Server lässt sich wecken.
Systemsteuerung\Alle Systemsteuerungselemente\Windows-Firewall -> Erweiterte Einstellungen
Windows-Firewall mit erweiterter Sicherheit: Ausgehende Regeln -> Neue Regel -> Regeltyp: Port -> Weiter -> UDP, Bestimmte Remoteports: 9 -> weiter -> Verbindung zulassen -> weiter, weiter -> Name der Regel eingeben -> Fertig stellen
Ich nutze dafür dieses Tool unter Windows:
http://oette.wordpress.com/wol2/
Ich habe z.B. bei mir im BIOS auch nicht die Möglichkeit es einzustellen, es funktioniert aber trotzdem. Die Option fehlt einfach. Bei meinem Server setzt ein Script den WOL-Modus des NIC automatisch auf g. Fährt bei mir der Server z.B. mal aus irgendeinem Grund nicht hoch, funktioniert auch WOL nicht, bevor der Server einmal das Script vorm ausschalten ausgeführt hat. Unter Windows "sollte" das automatisch geschehen, wenn es beim Treiber aktiviert ist.
Zum Vergleich einmal versuchen über die Oberfläche mit der WitzBox und einmal mit dem Desktop-PC zu wecken.
PS: Unter Windows eine Konfigurationsänderung zu beschreiben ist echt sowas von umständlich :-D