After Overstay Access Denied. Different Info from Embassies & PF.

I've never heard of a case like this, but let's get into it.  Please remember in reading what follows, that people on expat.com don't offer legal advice:  this is amateurs helping amateurs -- well-informed, perhaps, but totally informal.
First, to make sure that I understand the details, your tourist visa expired on February 25, 2016 (German citizens can stay in Brazil 90 days in every 180, with no extensions allowed), and you overstayed ten days less than  three years, departing on February 15, 2019 -- correct so far?
Second, as far as you know, the Brazilian authorities have no reason, aside from your visa overstay, to object to your return to Brazil, correct?  If you ran afoul of the police in any way during your overstay, that could be counting against you.
If the above is true, then you should have been allowed to pay your fine on arrival (as you were prepared to do); that would have cleared your record, and you should have been free to enter.
Since that didn't happen, you need to know why, and only the Federal Police, probably at Guarulhos, can tell you.  In your place, I would ask my fiancé to engage an attorney to contact the Federal Police on your behalf, and get documentation of your exact status.  Registering your união estável the day before your visa expired probably looked suspicious the the Federal Police, but the fact that you've been trying to get back ever since is in your favor, so make sure that the attorney is aware of all the circumstances.
If there's no impediment to your returning to Brazil, I would request a VITEM XI, a temporary visa for family reunion, on the basis of your união estável, from the nearest Brazilian Consulate in Germany.  That will give you an approved visa in your passport, and proof that your status with your partner has been reviewed by the Consulate.  It will also take you out of the "Tourist" pool and put you in the candidate pool for permanent resident.
Applying for a VITEM XI will require notarized Brazilian documents from your partner; if s/he can join you in Germany for the application, that would be helpful.  If you're planning on getting married anyway, you could also get married in Germany and register your marriage with the Consulate; this could also help your application.
Once you're admitted to Brazil on your VITEM XI, you'll have 90 days to request your CRNM (which replaced the RNE/CIE) from the Federal Police -- but you'll want to do it ASAP.  The list of required documents has now become pretty stable, and is available on the Federal Police website.
Best of luck.  Please let us know of your progress.

This is a difficult one.
Over stay almost 3 years and last minute had a domestic partners agreement. I do not want to guess, but are a few "red flags" there alone.
How did you survive for almost 3 years? Hope you did not work without a permit?
As stated you need to work with the nearest consulate face to face.
It took almost a year for an RNE ( CRNM now) for me, but I started as soon as I arrived and was given a "protocol #" which allowed me to stay until final determination.

abthree wrote:

And you overstayed ten days less than  three years, departing on February 15, 2019 -- correct so far?

That is correct, yes.

abthree wrote:

Second, as far as you know, the Brazilian authorities have no reason, aside from your visa overstay, to object to your return to Brazil, correct?  If you ran afoul of the police in any way during your overstay, that could be counting against you.

I never ran afoul from them, I always did what the PF asked from me. Another fact why I don't get whats happening.

abthree wrote:

If there's no impediment to your returning to Brazil, I would request a VITEM XI, a temporary visa for family reunion, on the basis of your união estável, from the nearest Brazilian Consulate in Germany.

I wrote with the Embassy in Munich about the Vitem XI. They said that they cant say if I have an impediment on me until the Visa is fully made and then sent to the PF for approval. I guess I have to do it that way in this case.

Texanbrazil wrote:

How did you survive for almost 3 years? Hope you did not work without a permit?

No, I never would have done that. My family sent me money every month until I finally would have been able to earn it myself. I was also asked this question by the PF and luckily had bank statements to proof that.

It would be a very good idea to have someone determine with the Federal Police in Guarulhos whether your name is flagged there as "do not admit", and if so, how you can get it cleared,  before you and your partner go to the trouble and expense of applying for a VITEM XI.  Remember, a visa is only permission to request admission to a country at a port of entry:  an immigration officer can still refuse to admit you, visa or not, as you've already learned.
If you're applying for a visa, I think that a VITEM XI is the way to go.  Be careful to satisfy all of the document requirements exactly, to save time; it would be wise to gather the documents that you'll need to request your CRNM at the same time.  Note  that the document requirements for the VITEM XI and for your CRNM once you get to Brazil are different, and even when they require the same document, you'll need two originals, one for the Consulate General in Munich, and one for the Federal Police in Brazil.  In addition, while the Consulate General will probably accept official German documents in German, and not require additional authentication, the German documents that you submit to the Federal Police will need to have apostilles attached, and have Sworn Translations (which you can obtain in Brazil) from German to Portuguese.
Please do post any additional questions.  Good luck!

Still scratching my head as to over stay by almost 3 years and not "running a foul" with PF.
Apply for a CRNM with you have overstayed may have put you into that issue. Did the PF give you a Protocol?

Man. I've got a similar situation. I hope you can get more info or share your experiences. It's so hard to predict what's going to happen with Brazilian PF, etc. because it all depends on the individual you talk to.

I entered Brazil in March 2016 on a tourist visa. I ended up overstaying my tourist visa and eventually getting a stable union with my Brazilian girlfriend and we later had our wedding ceremony, etc.  I was never able to get any sort of legal status from my stable union because my documentation didnt arrive in time and I basically couldn't legally file for any sort of status.  I left Brazil in Sept 2018 when we moved back to the U.S.  Of course I was hit with a R$10,000 fine when I left which I will have to pay when I return. So in total I overstayed by like 27 months.  I dont remember if I questioned the immigration officer when I left the country about when I could return, etc.

Now, I've been in the U.S. over a year and my wife's sister is getting married in Brazil in January of 2020.  So we are planning a trip.  At that time, I will have been out of Brazil for about 16 months.  I have a lot of the same questions as the original poster.  I, of course, really don't want to buy a flight to Brazil and then be turned away by immigration who may say "well... you overstayed by 27 months so 16 months is not a long enough absence from the country before you can return."   I kind of assumed if Brazil is standing to collect R$10,000 then they have an incentive to let the person in, but that is clearly not the case based on the experience of the original poster. 

Does anyone know how the PF identify people when they return?  Is it by fingerprints or just name, etc?  I dont recall if they have my fingerprints.  I lost my old passport with all my Brazilian visas and stamps so my new passport will be completely empty, dont know if the number will be the same.  Is it possible that with a new passport and no stamp evidence of previous trips to Brazil that they might just wave me in?  Would it make a difference if I filed for a permanent resident visa at the Brazilian consulate in the U.S. and tried to enter on a permanent resident visa?  Would I be able to avoid paying the fine?  Or at least guarantee entry?  Is there anyone that people can actually call to get accurate information in advance?  This R$10,000 fine situation is so new that I was surprised to even find someone who had already returned to Brazil after leaving with a R$10,000 fine.  Is there a usual way to calculate the amount of time that you need to stay out of the country?  I kind of understand why the original commenter was turned away because he was there for 4 years and then only out of the country for 3 months before returning... so that makes sense kind of.  But i will have been out of the country for 16 months. Is that enough time?  It's such a guessing game in Brazil.

Also I read the responses and suggestions, such as the VITEM XI, which I will definitely look into.

Hilliard,
A lot to unpack here.  Let's start with the easier stuff.
Yes, you should arrive prepared to pay the fine.  It's been in place since the current immigration laws went into effect in November 2017.  The PF computer systems were updated at that time and a lot of records were erased, but since you left the country in September 2018, I'm assuming that there's a record of your departure.  So, arrive prepared to pay, but don't volunteer -- wait for them to ask you.  If they don't, they don't, and probably won't in the future.
Length of stay is supposed to be calculated on a rolling 12 month basis, so, in spite of the 27 month overstay, once you passed the anniversary date of your last departure in September, you should be ok for admission.
Your new passport will have a new number.  They'll probably identify you from the biometric information in the new passport, which will match the old one.  They won't fingerprint you, though.
With respect to the type of visa, it depends on your plans.  Do you intend to request permanent residency while you're here, and live in Brazil?  If so, you want to apply for a VITEM XI, with your Brazilian marriage certificate (I'm assuming that you were married in Brazil, from your narrative) and the other required documentation.  In this case, see the list of documents that the PF require for permanence, and bring those with you as well.  If not, then you can enter as a tourist under the tourist visa waiver.
In principle, you should be able to get answers in advance either from the nearest Brazilian Consulate, or from the "Estrangeiros" section of the PF office that serves the city where you'll be going.  You can try emailing the Consulate, or calling the "Estrangeiros" section; it's doubtful that anyone will commit to anything, though.

As abthree stated, BR does not have finger/hand scanners at the first line of immigration's. Now if called to secondary, yes they have scanners. I enjoy walking around with my BIL at the airport and see a lot of things as to Immigration's and Custom's.

Hey,

a lot of updates on my side of the situation by now. We hired a lawyer to solve this since it was way off the charts to get our head around this. The thing is this. It didnt stay at 10.000 Reais. Apparently when you stay out of the country for a certain amount of time, the multa increases. A kind of "interest fee" as we were told. My lawyer went three times to the "Delegacia Especial de Policia Federal no Aeroporto Internacional de Sao Paulo/Guarulhos" and my fine was raised to a total of 13.257 R$, which I wired to my spouse and she payed it in Brazil. I brought the Comprovante with me to the airport. So be prepared to NOT only stick to your 10.000 as stated on your Multa that they gave you as you left the country. Its requested, or was from me, to pay it upfront. I needed to send a payment confirmation for my Lawyer so that the PF even continued negotiations. I dont get it why some people can just pay it at the airport.

Second thing, I came in way to early. I thought it was 90 days as the embassies told me, yeah. It was 180 days in my case. Might vary for the duration of such a long overstay, so in any case get a lawyer since its a similar case even though you reached more as I did with your marriage. Also, as someone else said I havent been fingerprinted as I arrived at the Airport (Im back in Brazil again now). But I immediately got asked if I have a set of papers stating if I am allowed to be here. I have a special visa from the delegation allowing me Entrance in a duration from August 2019 - February 2020, E Mails between my lawyer and the head of the airports PF and this comprovante, Airline return tickets and my previous stamps in the passport that I had to show. During this time my lawyer is working on a Perm Visa and an Extension since I came in with a normal Tourist Visa of 3 months.

Good info. Thanks

Thanks.
Glad that you made it back, and apparently have a competent attorney.   Good luck!

*ETA*  Stays for EU citizens (unless their countries had previously agreed otherwise with Brazil) are calculated on a rolling 180 day basis.  Stays for US citizens are calculated on a rolling 365 days.

Wow,wow,Wowzer...flipping nightmare...I thought something was wrong with the Re-entry dates when I first peeped this post, yet I kept reading ...kkk.... Glad all is well and gotta love "Beautiful Bountiful Brasil"....it is so difficult for the powers that be to be on the same page...
AB3 I follow total "No One Will Commit " to anything , thus flying by the seat of the pants and making up Rules as One goes gets frustrating most days...
All my Concerns and Documents were Presented to me within 90 days after my marriage..I thank the Higher Power and Beautiful Bountiful Belem for all was done with out a hitch,buggy or post to tie the thingy up to....

@abthree you say that stays for a US citizen are calculated on a rolling 365 days. Does this mean that an American must stay out of Brazil for an entire year after overstaying for several years?

08/15/22 @abthree you say that stays for a US citizen are calculated on a rolling 365 days. Does this mean that an American must stay out of Brazil for an entire year after overstaying for several years?

- @KillyRedd