So here's how it is. My friend who lives abroad had registered me a couple days ago, when the server was down. I accidently deleted them when clearing out my list. A day before the deletion, they changed their router.
So today, we're trying to re-add. The friendcodes are shown as correct, but the 3ds is acting as if the other person had not added them. (Showing a provisionally registered friend)
We've triple checked the friend codes, added, re-added, turned off, turned on, updated, held it sideways, smack our heads on the table and no longer know what to do.