6 Options, I would go with 6
You state you want "proportional sizes" so I will stick to these in the earlier examples although other non-proportional options exist.
(1) Add a second attribute to the table with the same name (add _1) and the same type (say integer) as the original. Copy all the values up to the thousands into the new attribute. Now let's say your high value is 5,000. For the three outliers in the millions change the value of these to 5001. Now you can merely state in the legend something similar to below.
0 - 2500
2500 - 5000
5000+
You should note somewhere that you have done this (methods or a text at the bottom of the map).
You can even add a halo or similar to these three on the final map to denote them.
(2) Make two feature classes, one of just the good stuff and one of the outliers.
The good stuff can be done as you state in your question.
The three in the millions can be donated with a symbol that is larger than the other max symbol but matches in any other manner but use a different outline. Now the three with the different outline fit in the map and the legend but you get to explain that these are much larger.
(3) Just use graduated symbol as you do but change the three "millions" symbols manually to the biggest size not to block the others.
(4) Make a huge map.
(5) Change the symbol size in proportional symbols to something much smaller.
(6) Proportional symbols are a bad option when three 1/5 of your data are massively outside the range of the rest of the data. Use something else.
Tell the reader what you did if you do 1-3.
