Using the relay to disconnect the neutral line doesn't really sound like you know what you're doing. You're exactly wrong in the safety department. In a perfect world, it's the hot that you want to switch. With only neutral switched, the heating coil is always energized, waiting to shock you.
Additionally, relying on a polarized electrical cord to try to make sure it's the hot you're switching has its own problems. You're better off using a double pole relay to fully disconnect the toaster from the electrical supply. Use a relay that is designed specifically to switch both legs of a power supply.
Also don't need to heat-shrink, glue, or electrical tape the wires, that's overkill and amateur hour. Hiding things in an attempt to increase safety is a sure way to decrease safety.
Use the project box, and mount your circuitry (including relay) on perf board. Simply solder the relay inline on the hot wire. Keep your low voltage relay control wiring (and arduino circuitry) physically separate from the relay and line voltage power wires. Do not let low voltage and high voltage come near each other, except at the relay, and even then, those come from different directions. Physically secure the power wires so they can't accidentally be pulled out. Be neat.
Your heating coils should be shielded from your pcb by a heat spreader, and your thermocouple should be next to the pcb, and not be touching anything. It's the air that heats up the pcb, and the air that heats up the thermocouple. You trying to bake the pcb, not broil it.
IMPORTANT SAFETY NOTE:
The electrical power that comes out of your outlets is extremely dangerous. It's not the fun-times easygoing stuff of 15 volts and below. It will surprise you, and given the opportunity, it will kill you.
From your question, you really don't seem to know what you're doing. I'm not trying to insult you, I just don't want you to die. Advice from the internet is not going to make this any safer. Sit down with someone in the real world who has worked PROFESSIONALLY with household electrical circuits and have them look over what you are doing.
Please be safe.
Very interesting. My guess would be that when some large piece of machinery switches off (or on), it causes a huge shift in ground current that extends through your property, and this impulse is what's tripping your RCDs. You probably wouldn't see this on a multimeter; you'd need a datalogger with a reasonably high sample rate to catch it.
I'm thinking that to solve the problem within your firm, you'll need to carefully isolate all of the ground connections for every piece of equipment downstream of the RCDs and tie them back to a single point, like they do in hospitals for sensitive equipment (usually indicated by an orange-colored outlet or other marking). However, depending on how extensive your facilities are, this could get to be as expensive as an UPS (but would be lower maintenance, long-term).
The other approach would be to get the power company involved and see whether they can make any adjustments at the substation or have any other advice for you.
Best Answer
What you're looking for is some kind of IEC Power Entry component. Digi-Key and other distributors have tons, with or without fuses, and with and without protective earthing. Personally, I like using the ATX power supply style IEC C-14 connectors, because I have tons of those cables laying around. This one also has a built-in fuse holder (remember to also get fuses!) http://www.digikey.com/product-detail/en/723W-X2%2F03/Q205-ND/245546