a) Actually, it seems to be (almost?) support as eZContentObjectTreeNode::createSortingSQLStrings is used in eZContentObject::relatedObjects. So have you tried it even if it isn't documented?
b) That is possible as of 4.2, with the introduction of node_id and contentobject_id filters and storing options.
Actually, I have tried using the attribute_id as a sorting option. In combination with setting the option 'attribute_identifier' this caused a MySQL error (eZMySQLDB: Column 'contentclassattribute_id' in where clause is ambiguous.) and seeing as the documentation said that this sorting option was not supported I concluded that it wasn't possible.
Just now I dropped the 'attribute_identifier' option and used 'all_relations' and this appears to work in combination with the unsupported sorting option (at least I'm not getting any errors). So now I'm checking on the existence of the attribute identifier in the returned resultset and it seems that I'm in business :-). Thanx!