Great responses from Robert and Andy below that pretty much cover a lot of what you need to think about.
I don't know your industry and how competitive it is or your market and how broad that is (local / regional / national / world) so any real targeted advice is tough.
Also, Looking at your budget, you are not going to get a lot of SEO for £750 a month from an established agency. If you want content and links developing that kind of figure is just not going to do the job if you outsource it.
You could consider taking on an apprentice or someone interested in Internet Marketing and wanting to cut their teeth. This way, you could get a full time resource, someone who can tap into the masses of information out there and really do something with it.
If you can find someone who can research and write content and is happy with the more technical side of things as well great but the focus should be on someone who can create the kind of content you need to broaden your scope and earn you links.
There is just so much good information out there that if someone can come into your business, learn what you do and then use that knowledge to create valuable content, big content and promote it socially and via outreach to get links then certainly, six months with an approach like that will benefit you far more than six days with an agency over a six month time period.
You could potentially even use an agency to come up with a six month plan for you with a mind to have an in house
Consider the link bait guide from Distilled. Primarly produced by Ed Fry, a 16 year old intern. It has now earned around 500 links. This is not only a great resource for someone with a lot of time it is also a great example of what can be accomplished with time and dedication.
My advice would be to think about getting an intern for six months. Work with an agency to fashion a plan involving search, social, content, outreach etc and then use your intern to do the graft.
Some interesting reading from this perspective:
http://www.distilled.net/linkbait-guide/
http://www.seomoz.org/blog/the-noob-guide-to-online-marketing-with-giant-infographic-11928
http://www.seomoz.org/blog/the-noob-guide-to-link-building
In this game you have to be practical and whilst skill and experience count for a lot on the strategic end, you can't get away from the need to do some great work to create the content and then the talk required to get the message out and get people to link to it and all of that takes time and effort.
I go into how to hustle for links a bit more here: http://www.bowlerhat.co.uk/blog/earning-links-work-talk-hustle/
Hope that helps!
Marcus
P.S. Avoid the $99 package - that can't be any kind of good.