Very interesting topic!
I've somewhat been on all sides of the fence. In the old days (okay the 90's) I had a variety of people and companies that referred SEO work to me (yes, that includes Danny Sullivan himself

). In those cases, they would simply tell the contact to say they were referred by so and so, and then if anything ever came of the job, I would pay out 10 or 15% of the total as a referral fee. (I can't remember which percentage it was...I think maybe 15.)
I like working that way because you still have to sell the client on your services, and still get to work directly with the client with no middleman.
Over the years I have been approached by agencies and the like to do it the other way where the client goes through the agency and I work behind the scenes. In those cases, I would have still given them the 15% referral fee and then they could mark it up however they wanted. None of those potential jobs ever came though, however, so I don't know whether I would have liked it or not. The middleman thing kinda seems like it could be a bit of a pain.
Now I'm not taking referrals any more as I have more work than I can handle, and am instead contracting some aspects out to people. I've always contracted out copywriting and link building and stuff, and I prefer to not hide the fact that I'm not doing the work myself. I strongly believe in giving credit where credit is due.
I simply charge whatever I charge and then pay the contractors their going fees for their services. Often the work goes through me because I take full responsibility for any client work and usually have to at least give it a cursory glance. But if necessary, the contractors will deal directly with the clients too. I know Debra prefers to work that way for link building.
On occasion, I sometimes refer leads for full SEO jobs out to other companies if the client needs it done more quickly than I can do it. In those cases, I would then get a referral fee if things worked out and moved forward.
I always paid my referral fees when the job was completely finished and I had received full payment.
I pay my subcontractors on whatever terms they have, such as full payment in advance, or payment when the job is done. My subcontractors have worked with me enough to not worry about getting paid, so we usually just invoice and pay when we get around to it!
As to testimonials and stuff, since most of my subcontractors are known to my clients, they are free to say that they worked for that particular client's site, in whatever capacity they worked on it. I suppose technically, I'm their client and not the other client, but as far as I'm concerned, they should be entitled to claim ownership of their own work!
Many copywriters don't mind not getting credit and working as a ghost writer, but I just feel weird about working that way.
Jill