Где и как быстрее — не знаю. Не очень понимаю, что и как муж будет подавать в SEF, если вы говорили, что он там уже был и у него ничего не приняли. Также не очень понимаю о каком апостиле и переводе идёт речь? У вас нет португальского свидетельства о браке? Ваш муж за три года не зарегистрировал его в Португалии? Тогда понятно, почему все службы с настороженностью относятся к вашему браку и вашим документам... В соответствии со статьёй 1651 Гражданского Кодекса Португалии такая регистрация обязательна.
Если вы говорите, что в Консульстве вам всё понятно объяснили, то какие остались вопросы? Вы считаете, что если на форуме что-то посоветуют отличающееся от первоисточника (Консульство), то это будет иметь смысл? Мне кажется, что надо действовать именно так, как советуют органы, которые будут рассматривать ваши бумаги. Так соберите всё, что попросили в Консульстве и подавайте заявление. Если скажут дополнительно обратиться в SEF до получения визы в Москве, то обратитесь и туда. В любом случае для въезда в Португалию вам требуется виза, а поставить её может только Консульство.
Самый правильный способ — действовать по существующим правилам.