Which of these processors would you recommend to me, and why? (Everyone of them X2)

A 5600+ Brisbane is 2.9ghz and uses only 65 watts, so I'd have to recommend that one over the 6400+.  The 6400+ gives you an extra 300Mhz and double the L2 cache, but uses 125 watts.  There are also 5600+ Windors, however.  Although they use 89 watts and are 2.8ghz, they have double the cache of the Brisbane and thus usually are better.

If you don't care about power, them the 6400+ is the best of course.  But I recommend the 5600+ Windsor, followed next by the 5600+ Brisbane.  No need to go any lower (5200+).  And I haven't really heard of a 5800+, but link me to it if you can. 

5600+ Brisbane 2.9GHz 2x512KB L2 Cache 65w

5600+ Windsor 2.8GHz 2x1MB L2 Cache 89w

6400+ Windsor 3.2Ghz 2x1MB L2 Cache 125w 

I'd guess your current 3800+ is 2.0Ghz 2x512KB L2 Cache 89w.  So you can already do 89w.  The jump to 125w may be alright, but many motherboards cannot support it.  Though I think yours can.  Regardless, I'd really commened the 5600+, either version.

The M2N-MX can support it with a BIOS update (It is a good board for a micro ATX which is why i built it into my Mom's system :P ). If you don't update the bios it will not recognize the CPU properly but it will post. the 125W parts do get a bit hotter and like it has been already said consume a great deal more power. So it is all up to you in the end. But it would not be a huge dramatic jump in performance over what you have now.

Thanks to both of you! How many watts uses the x2 5200+?

65w.  So no advantage over the 5600+.  Update your motherboard and go for the 6400+ if you want what's best performing.  Just make sure your power supply can take the extra juice.  Or if you are a fan of less power, go for the 5600+ Brisbane.  Gotta get as much performance as you can, right?

Are you buying online?  Link us if that is the case.