I'll try the baking method for shure, though I rather would like to use new tape..
I wouldn't bother baking it unless it's something precious that you want to digitize. For new recordings, just buy new tape. I'd do this as a matter of course when diagnosing a machine - take bad tape out of the equation.
(EDIT: Keep the reel, as an empty spool though. Just get the tape off it and throw that away.)
Where are the relays located, and Is there a solution for this? Cleaning them?
Sorry i'm a newbie in tapemachines, but I have experience with electronics and soldering boards...
I thought the shedded tape was the issue, because it smothered the heads so bad, and I figured the heads can't play or record with all the shed on them...
Should I also worry about cold solder joints? or failing components?
Get new tape first. Once that's out of the way, see what happens next. Relay faults tend to be per-channel - if you find that the odd channel doesn't record (or play back) that could be a relay issue, or a card seating problem or whatever.
FWIW, the relays are on the channel cards. I don't know the B16, but on TASCAM decks you generally have several of them, to switch the signal path around when you record and to mute playback etc.
The relays, being electromechanical, tend to stick as they age. Some of them you can dismantle and clean, but for the most part you'd replace them. Again, they tend to go intermittent on a per-channel basis, not all at once.
Aside from the rubber components (belts, roller) and relays, the other thing to watch out for component-wise is electrolytic capacitors, which dry out with age. Ideally you'd replace the lot, but ugh, that is so time consuming and fiddly. I still haven't fully recapped my 2-track, once I got it working 'well enough'.
If you have a dead, very noisy (or very quiet!) channel it may well be the caps, but as a rule the deck will work to some degree even with bad ones.