Can custom objects have a have many-to-many relationship with other custom objects?

Only if they are many-to-custom object relationships.

They can, but only in the pre-processing phase.

Yes.

They could in the previous version of Salesforce API.

Answer:
Yes.

Note: This Question is unanswered, help us to find answer for this one