電話番号であることを検証することはできますが、必須ではありませんか?現在のように、数字を入力しないとエラーが発生します。これを行うために正規表現を変更できることをどこかで読んだので、正規表現を(?:...?)で囲んでみました。
<asp:TextBox runat="server" ID="tbCompanyFax" Width="99%" Text='<%# Eval("CompanyFax")%>'></asp:TextBox>
<ajaxTK:MaskedEditExtender runat="server" ID="maskCompanyFax" AutoComplete="false" TargetControlID="tbCompanyFax" Mask="(999)999-9999" ClearMaskOnLostFocus="false" />
<asp:RegularExpressionValidator ID="regCompanyFax" runat="server" ControlToValidate="tbCompanyFax" ErrorMessage="Invalid Fax number" ValidationExpression="(?:((\(\d{3}\) ?)|(\d{3}-))?\d{3}-\d{4})?" Display="None"></asp:RegularExpressionValidator>