Can a single co-authored paper be part of two stapled dissertations (by two people)?

Every university should have guidelines around how publications can be incorporated into a PhD thesis. The correct advice (as @Andreas notes) is to consult these guidelines. Furthermore, it seems that PhD by publication is becoming more popular and guidelines are evolving.

I'm familiar with various models of "PhD by publication". At my institution in Australia, the PhD student is expected to be first author on any major publication that forms part of a PhD by publication submission. They also need to attach a form for each publication outlining their contribution and the contribution of the other authors. The form needs to be signed by the other authors. Non-first-author publications can be included but they are intended more as supplementary contributions. Exactly what this means is a little open to interpretation.

By way of a concrete example, here is an example of such a policy (the policy at your university may differ):

It is expected that the student will be the first author on the papers, as per 1 above; the number of co-authors is limitless. Students may be second or later authors on additional papers.

Thus, to answer your specific question, at my institution, a paper could be included in more than one PhD. However, the student who is first author would have a stronger inherent case for it being seen as an integral part of their thesis. Furthermore, the contributions of all authors would have to be explained.

You may want to consider practical alternatives such as thinking about how the work could form two papers where you each drive one paper as reflected in being first-author on that paper.

Depends on the (formal) rules of the university in question. At my University, rules state clearly that every PhD candidate needs at least one SCI indexed paper, authored as first author (!) to be eligible to submit his thesis, so the scenario you describes would not fly, only the author who is first, would be able to submit the thesis, based on that paper.

For a "stapled" dissertations, at my Uni, all papers (usually no less than three SCI indexed journal papers) have to be authored by the thesis author as the first author. Situation is further complicated by the fact that they are at different universities, so Bob should really take care that he won't slam shut his own door to dissertation by allowing incorporation of his paper into someone other's thesis (in case Bob is the first author).

Consider the following scenario which may end disastrously for Bob: Alice submits her dissertation with Bob's (first-authored) paper and she is granted PhD, based on her Uni rules. Later, Bob tries to do the same, but is rebuffed by the thesis examiner, who finds the paper to be already part of some other dissertation, and the Bob's uni rules do not allow for that...