Due to buggy hardware or drivers, your monitor's correct resolutions may not always be detected. For example, the EDID data block queried from your monitor may be incorrect.
If the mode already exists, but just isn't associated for the particular output, you can add it like this:
$ xrandr --addmode S-video 800x600
If the mode doesn't yet exist, you'll need to create it first by specifying a modeline:
$ xrandr --newmode
You may create a modeline using the gtf or cvt utility. For example, if you want to add a mode with resolution 800x600, you can enter the following command: (The output is shown following.)
$ cvt 800 600 # 800x600 59.86 Hz
(CVT 0.48M3) hsync: 37.35 kHz; pclk:
38.25 MHz Modeline "800x600_60.00" 38.25 800 832 912 1024 600 603 607 624 -hsync +vsync
Then copy the information after the word "Modeline" into the xrandr command:
$ xrandr --newmode "800x600_60.00"
38.25 800 832 912 1024 600 603 607 624 -hsync +vsync
After the mode is entered, it needs to be added to the output using the --addmode command as explained above.
Source: https://wiki.ubuntu.com/X/Config/Resolution
Not 100% sure because you've got Intel graphics, but it sounds like the good old trouble with bad EDID. In a nutshell, your monitor sends bad info to your graphic card, it cannot read the maximal frequencies and errs on the side of caution, using the lowest possible settings only.
randr is (by design!) only meant for run-time changes. For any permanent configuration, you need to change your X server settings. For this, edit /etc/X11/xorg.conf (This is an important system file! Make a backup first!). You need to add HorizSync and VertRefresh lines. The result should look like this:
Section "Monitor"
Identifier "Configured Monitor"
HorizSync 30-35
VertRefresh 55-75
EndSection
Warning: Do not use the numbers I posted here! If you set a frequency in HorizSync which is too high, it might permanently damage your monitor. They fluctuate considerably between monitor models, I've seen them anywhere between 30 Hz and 75 Hz. You should look up the correct values in the monitor's user guide, or call the manufacturer's tech support and ask about vertical and horizontal frequency at your preferred resolution.
Maybe you'll need to add the mode line to the Xorg.conf manually (I forgot which section, I think Screen) but probably after the X restart you'll be able to set the resolution using the built-in graphical tool.
Even if this doesn't solve your problem, the xorg.conf is the place to save permanent changes to your screen configuration.
Edit, as an answer to your comments.
The HorizSync is the frequency, yes. On a nVidia card, setting the HorizSync and VertRefresh in the xorg.conf (then restarting X or just rebooting) makes all the usual resolutions available in the nVidia driver GUI. So choosing your preferred resolution there should be possible.
If this doesn't happen with the Intel drivers, you can manually add the resolution you want into your Xorg.conf. Still in the Monitor section, paste your modeline (which worked with xRandR). Then list the mode name as the Preferred mode option. Then, in the Screen section, Display subsection, add a Modes line, including the name of your mode.
The result should be something like this:
Section "Monitor"
Identifier "Configured Monitor"
HorizSync 30-80
VertRefresh 55-75
Modeline "1152x864_60.00" 81.75 1152 1216 1336 1520 864 867 871 897 -hsync +vsync
Option "PreferredMode" "1152x864_60.00"
EndSection
and below that, within the Screen section
SubSection "Display"
Depth 24
Modes "1152x864" "1024x768" "640x480"
EndSubSection
I am not sure if you need the Display subsection, but I have found it in an old config file of mine. If it doesn't work, comment it out again. Cannot test it on my current system because I cannot restart just now, and my current monitor configuration is different. So it may still need some tweaking. But in theory, adding the modeline into Xorg.conf is the permanent version of adding it dynamically to RandR.
If you need to tweak, a good information source would be the Xorg.conf manual. http://www.x.org/archive/X11R6.8.0/doc/xorg.conf.5.html
If all else fails, I think there is a X profile file where you can add xRandR commands. It is certainly not elegant, and possibly as slow as your init script solution. Besides, I don't remember much about this file and how to use it, so cannot help you there.
And if these things fail too, maybe the problem is something else. As it is probably still X related, you could look into your /var/log/xorg.0.log file. If there are lines starting with (WW) or (EE), google these lines and you'll almost certainly find a solution.
Best Answer
It sounds like you are using the vino server to share the desktop via VNC. Although I think you can change your /etc/X11/xorg.conf, or whatever the X config file is now, I have another suggestion. Leave the X config alone and create another session for your vnc.
Install vnc
Create vnc start and stop scripts
vnc.sh
vnc-kill.sh
12 is just an arbitrary display number. You will use this when you connect to the server. It can be any number except 0. That is what the vino server uses by default (I think). Don't forget to chmod +x the scripts.
Optional: Start vnc session on boot
Add the vnc.sh to your /etc/rc.local so that the session will start when the computer starts. sudo vi /etc/rc.local and add this to the end before the "exit 0"
I run the vnc server as a user here. I don't want the server to run under the root context. Replace the "YourUserName", of course. Alternatively, you do not need to put this here, you could ssh in and run the "vnc.sh" script manually. Your call.
Set your vnc password
(this is separate from the other vnc desktop password)
Edit your vnc session file
Comment out everything and put this at the end
Test it
Run your vnc.sh script and connect from another computer.