Question: Well, the internet is working flawless, all the sites are fine, and I can use my webmail from the provider website, althought I can't **send** anything from Outlook, funnily I receive everything, and all computers here use Outlook, also, tried Thunderbird, same happens. 

I tried to ping and do tracert's from the command line, and they all time out, even if I try to ping Google.com and I also have a Yahoo account with the same issue, so it's not my provider fault, the tracert stop at the router. I removed all blocks from the router, disabled everything, my router firewall is right now all in mininum security.

I also tried to restart several times, and once in a while the mails are sent
I'm really lost...

UPDATE: If I change the DNS server suddenly everything works for some 30 minutes, then everything is blocked again, maybe my ip is being blocked?

Answer: 
some ISPs will block outbound mail to everything but their mailservers to stop people from sending spam from their local connection. 

I'd call your ISP and ask them if they are blocking outbound email.
Having another, external site show the same behavior does not prove your provider is not at fault. Having some work while others do not would point the finger away from them, but not completely. @Mike is right in the answer below. Having no working examples of sending SMTP is actually indicative of possible provider blocking. 

Try to telnet to a couple of SMTP servers on port 25, see if you get a "helo". If it is blocked, you can ask your ISP why they're blocking, not whether they are.