I have this code:

import java.awt.Graphics;
import java.awt.event.ActionEvent;
import java.awt.event.ActionListener;
import java.awt.event.KeyEvent;
import java.awt.event.KeyListener;

import javax.swing.JFrame;
import javax.swing.JPanel;
import javax.swing.Timer;

public class Game extends JPanel implements KeyListener {
  /* Game Panel class containing all functions */

  JFrame mainFrame = new JFrame("Game");
  boolean needs_repaint;

  public void paintComponent(Graphics g) {
    /* Draws the elements on the screen */
    super.paintComponent(g);

    System.out.printf("Panel Width: %d\n", this.getWidth());
    System.out.printf("Frame Width: %d\n", this.getParent().getWidth());

    /* Repainting has finished */
    needs_repaint = false;
  }

  public void update() {
    /* Main game loop */
   
    /* Always repaint */
    //this.repaint();
  }

  public void run() {
    /* Displays the frame, start the game */
    mainFrame.setVisible(true);
    this.requestFocus();
  }

  public Game() {
    /* Defines the frame and the game panel */
    this.setFocusable(true);
    this.addKeyListener(this);

    /* Fixed Layout frame */
    mainFrame.setSize(852, 600);
    mainFrame.setResizable(false);
    mainFrame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
    mainFrame.getContentPane().add(this);   // Add game panel to main frame

    /* Start timer with main game loop */
    Timer timer = new Timer(25, new ActionListener() {
      public void actionPerformed(ActionEvent e) {
        update();
      }});
    timer.start();
  }

  /* Game Class is not abstract, and these functions are not needed */
  public void keyPressed(KeyEvent key) {}
  public void keyReleased(KeyEvent arg0) {}
  public void keyTyped(KeyEvent arg0) {}
 
  public static void main(String[] args) {
    new Game().run();
  }
}
Basically, what happens is that the frame and the panel not always have the same width. This happens in my game Falling Blocks and with the above code as well. Below is what happened when I ran the program several times (it's a bit random, sometimes it has 850, other times it has not).

I have no idea of how to fix this, since my code supposedly gives the frame a fixed size of 852.

david@davidbuntu:~/temp$ java Game
Panel Width: 850
Frame Width: 850
Panel Width: 850
Frame Width: 850
Panel Width: 842
Frame Width: 842
Panel Width: 850
Frame Width: 850
david@davidbuntu:~/temp$ java Game
Panel Width: 850
Frame Width: 850
Panel Width: 850
Frame Width: 850
david@davidbuntu:~/temp$ java Game
Panel Width: 850
Frame Width: 850
Panel Width: 850
Frame Width: 850
david@davidbuntu:~/temp$ java Game
Panel Width: 836
Frame Width: 836
Panel Width: 842
Frame Width: 842
Panel Width: 836
Frame Width: 836
david@davidbuntu:~/temp$

EDIT: As you can see I also set mainFrame to not resizable, so I'm not resizing it.

I believe the issue is that setting the size only sets the current size; what it is right now. It does not set the size you want it to be, after various calls have been made. Disabling resizing is for preventing the user from resizing the component, it doesn't turn resizing off.

In my own code I do:
        Dimension size = new Dimension(width, height);
        setSize(size);
        setMinimumSize(size);
        setMaximumSize(size);
        setPreferredSize(size);

You should also probably call 'pack' on the frame, after setting the size and before you make it visible.

I have added the code I suggested, but for the JPanel, to your original code, and it works fine for me.
import java.awt.Dimension;
import java.awt.Graphics;
import java.awt.event.ActionEvent;
import java.awt.event.ActionListener;
import java.awt.event.KeyEvent;
import java.awt.event.KeyListener;

import javax.swing.JFrame;
import javax.swing.JPanel;
import javax.swing.Timer;

public class MainFrame extends JPanel implements KeyListener {
  /* Game Panel class containing all functions */

  private JFrame mainFrame;
  private boolean needs_repaint;

  public void paintComponent(Graphics g) {
    /* Draws the elements on the screen */
    super.paintComponent(g);

    System.out.printf("Panel Width: %d\n", this.getWidth());
    System.out.printf("Frame Width: %d\n", this.getParent().getWidth());

    /* Repainting has finished */
    needs_repaint = false;
  }

  public void update() {
    /* Main game loop */
    
    /* Always repaint */
    //this.repaint();
  }

  public void run() {
    /* Displays the frame, start the game */
    mainFrame.setVisible(true);
    this.requestFocus();
  }

  public MainFrame() {
    /* Defines the frame and the game panel */
    this.setFocusable(true);
    this.addKeyListener(this);

    /* Fixed Layout frame */
    Dimension size = new Dimension(850, 600);
    this.setSize(size);
    
    mainFrame = new JFrame("Game");
    mainFrame.setResizable(false);
    mainFrame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
    mainFrame.getContentPane().add(this);   // Add game panel to main frame
    mainFrame.pack();

    /* Start timer with main game loop */
    Timer timer = new Timer(25, new ActionListener() {
      public void actionPerformed(ActionEvent e) {
        update();
      }});
    timer.start();
  }

  /* Game Class is not abstract, and these functions are not needed */
  public void keyPressed(KeyEvent key) {}
  public void keyReleased(KeyEvent arg0) {}
  public void keyTyped(KeyEvent arg0) {}
  
  public static void main(String[] args) {
    new MainFrame().run();
  }
}

I had a similar problem to this when I wrote my own graphics engine, but it was around 5 years ago, so the solution is pretty hazy. If I remember correctly, it could be that the width is including other items in the JFrame, such as the surrounding border. However I don't know for sure. For safety I'd concentrate on checking the size of your inner JPanel, as this is the component where the size really matters, and not care what the outer frame is using.

I also added a call to pack, to ensure it's all packed down to the size you want.

Bump?

Well, the problem is if I don't set the size on the frame, then the panel won't be 800*600, right?

Here's an example, the frame appears very tiny when displayed.