I get what you're trying for (sounds interesting, btw), but you're making things harder than they need to be. The existence of the accent itself, as you've seen, should be enough for Max to call BS on the au pair story, which is, from what I'm gathering, all you need for the purposes of the story.
If you do decide to add the "he's fluent" element, you have three possibilities:
1) His native tongue is English, and he learned Portugese as a second language
2) His native tongue is Portugese, and English is the second language
3) He grew up speaking Portugese and English in equal measure and they can both be considered native tongues for him.
You didn't clarify which applies to Max, and it can make a big difference.
My first language is English, and I gained fluency in Italian as an adult. I can tell you parts of my own experiences that may or may not be useful.
1) I can spot an Italian accent in English fairly easily. Additionally, I can differentiate to some degree between English accented in languages that I don't speak. So, for example, if you played video clips of English accented with Russian, French, German, Arabic, and a few others, I could probably tell you which is which, despite lack of fluency in any of them. However, I'm familiar with the cadences of those languages. If you played clips of other languages, I'd probably be stumped.
On the flip side, I have much more difficulty picking out accents of any type in Italian. Indeed, on several occasions I astonished my Italian friends by understanding things that gave them trouble (period pieces, for example, and some very memorable conversations with a guy from southern Italy who spoke in accented dialect so thick that my Roman friends couldn't parse a word he said. I actually served as his translator, from Italian back into Italian). The reason for this was because to me, it was all part of the same whole. New words, old words, accents from here and there... as I was learning the language, I didn't know which was which. In my mind, it was a monolith, all equally indecipherable at first, and all equally understandable later on.
2) Ability to speak a language and ability to parse an accent are totally different skills. Someone can be good at one, both, or neither.
When you have an accent, as I did in Italy, the first question you'll hear in basically every conversation is "Where are you from?" Well, after a couple years of repeating, "I'm an American, blah, blah, blah," I decided to goof around with it, particularly when I was out drinking with friends and chatted with strangers I knew I'd probably never see again. I started telling people I was from whatever country popped into my head, trying to do someplace different every time. When I began doing this, I was sure people would call BS, but it worked EVERY SINGLE TIME. Despite the fact that I had an obvious American accent (I never could shed it properly), and look like... well, an old woman once told me that I had "the map of Ireland drawn on my face," so that should give you an idea, I easily convinced people that I was from every corner of the globe.
From this, I learned that while most people are excellent at recognizing "not from here," far fewer are able to differentiate between various accents with any degree of accuracy.
3) When two people discover, while speaking one language, that they're both fluent in another language, there's nearly always a brief exchange of pleasantries in that second language, even if they afterward switch back to the first language they were speaking. If you want to make Max fluent in Portugese either as a first or second language, then Elizabeth will also have to actually know the language (to varying degrees depending on Max's level of fluency) to pull off the ruse. Even if this is an exceptional circumstance and he skips this little ritual because he wants to hide his suspicion, it would be a simple matter for him to toss a Portuguese phrase or two into the conversation to see if she understands him.
Just some things to consider as you put your scene together.