I don't think it's possible to enforce that replaced_with can only occur if link='notusing'. You can make replaced_with optional using minOccurs='0', but that's about it.
If you are able to change the structure of the XML file, you could do something like this instead:
<?xml version="1.0" encoding="utf-8" ?>
<fontData
xmlns="someNamespace"
xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
xsi:schemaLocation="someNamespace XMLSchema1.xsd">
<fonts>
<font name="font1" />
<font name="font2" />
</fonts>
<obsoleteFonts>
<font name="font3" replaced_with="font2" />
</obsoleteFonts>
</fontData>
And then you could use key and keyref to enforce that the name of any font within obsoleteFonts exists in fonts.
Here's how the XSD file would look to enforce this XML format:
<?xml version="1.0" encoding="utf-8"?>
<xs:schema
xmlns="someNamespace"
xmlns:tns="someNamespace"
xmlns:xs="http://www.w3.org/2001/XMLSchema"
targetNamespace="someNamespace"
elementFormDefault="qualified">
<xs:element name="fontData" type="fontData">
<xs:key name="fontKey">
<xs:selector xpath="tns:fonts/tns:font" />
<xs:field xpath="@name" />
</xs:key>
<xs:keyref name="obsoleteFontToFontKeyRef" refer="fontKey">
<xs:selector xpath="tns:obsoleteFonts/tns:font" />
<xs:field xpath="@replaced_with" />
</xs:keyref>
</xs:element>
<xs:complexType name="fontData">
<xs:sequence>
<xs:element name="fonts" type="fonts" />
<xs:element name="obsoleteFonts" type="obsoleteFonts" />
</xs:sequence>
</xs:complexType>
<xs:complexType name="fonts">
<xs:sequence>
<xs:sequence>
<xs:element name="font" type="font" maxOccurs="unbounded" />
</xs:sequence>
</xs:sequence>
</xs:complexType>
<xs:complexType name="obsoleteFonts">
<xs:sequence>
<xs:sequence>
<xs:element name="font" type="obsoleteFont" maxOccurs="unbounded" />
</xs:sequence>
</xs:sequence>
</xs:complexType>
<xs:complexType name="font">
<xs:attribute name="name" type="xs:string" />
</xs:complexType>
<xs:complexType name="obsoleteFont">
<xs:attribute name="name" type="xs:string" />
<xs:attribute name="replaced_with" type="xs:string" />
</xs:complexType>
</xs:schema>
I tested this with the Visual Studio schema validator, but hopefully it will work properly in whatever technology you are using.