An example of the .NET web service accessing an SDE could look something like this
[WebMethod(Description = "Returns Flow Control History Details")]
public DataTable FlowControlHistory(String objectID)
{
 DataTable FlowTable = new DataTable();
 System.Data.OleDb.OleDbConnection connection = new System.Data.OleDb.OleDbConnection("<your connection string here>");
 connection.Open();
 // build a sql expression to access your database data
 // using a passed OBJECTID from a feature in flex
 string strSQL = "SELECT DISTINCT t1.FLOWID " +
     "FROM sde.SSCOMPLEXFLOWCONTROLHISTORY as t1 " +
     "WHERE t1.OBJECTID = '" + objectID + "' " +
     "UNION " +
     "SELECT DISTINCT t2.FLOWID " +
     "FROM sde.SSFLOWCONTROLHISTORY as t2 " +
     "WHERE t2.OBJECTID = '" + objectID + "' " +
     "ORDER BY FLOWID;
 System.Data.OleDb.OleDbDataAdapter Adapter = new System.Data.OleDb.OleDbDataAdapter(strSQL, connection);
 Adapter.Fill(FlowTable);
 try
 {
  FlowTable.TableName = "Table";
 }
 finally
 {
  connection.Close();
 }
 return FlowTable;
}
Then in Flex, you'd do something like this.
protected var service:WebService;
protected var retry:uint = 0;
// send your Web Service WSDL to define a web service
public function setWsdl(value:String):void {
 service = new WebService();
 service.showBusyCursor = true;
 service.wsdl = value;
 service.addEventListener(FaultEvent.FAULT, WsdlFault, false, 0, true);
 service.loadWSDL();
}
protected function onWsdlFault(fault:FaultEvent, token:Object = null):void {
 // I always try to load a web service twice if I get a load error.
 // Just in case, my network can laugh at me sometimes
 retry++;
 if (retry < 2)
  service.loadWSDL();
 else {
  service.removeEventListener(FaultEvent.FAULT, WsdlFault);
  Alert.show("A Web Service has failed to load. Please close the application and try again.", "Error");
 }
}
// function that will call my web service
public function findRelatedFlowData(objectID:String):void {
 var responder:AsyncResponder = new AsyncResponder(onFlowDataResults, onFault);
 var request:AsyncToken = service.FlowControlHistory(objectID);
 request.addResponder(responder);
}
proteced function onFlowDataResults(result:ResultEvent, token:Object = null):void {
 var ac:ArrayCollection = result.result.Tables.Table.Rows;
 // do something with results here
}
protected function onFault(fault:FaultEvent, token:Object = null):void {
 // I always try to load a web service twice.
 Alert.show("A Web Service error has occurred.", "Error");
}
This has always worked for me, plus by using C# or VB.NET you get a bit more control over your query. The relates in the ESRI API are still great and I use them for large data dumps, but I still have a lot of these unique queries of my SDE.