A solo miner (or a pool operator if they keep the fees) can use large transaction fees to avoid taint and network analysis. These algorithms must be updated to include transaction fees.
No, they can't. You just extend the taint-tracking through the newly minted coins (e.g. if you try to "melt" 75 BTC with the 25 BTC reward, then the resulting 100 BTC should be considered 75% tainted).
RE: orphans: orphans happen naturally when two nodes on the network find blocks at approximately the same time. Somebody should do a rigorous analysis to determine what are the most important factors affecting orphan rates (number of connections? quality of connections? bandwidth available to "blast out" the new block? block size? Number of not-previously-seen transactions included in the block?)