Most regional tourist boards apply a charge to list hotels and holiday properties but in many cases this cost is of little consequence to the revenue it can generate. I get a lot of this sort of thing from some of the hotels I've dealt with in the past, and there is simply no way of putting every B&B, hotel, holiday cottage or whatever at the top of any search engine rankings.
Without going off on one here, there are certain realities:
1. Unless it's the only property in its category in the region it will always have significant competition
2. There are now so many hotel/property letting sites that link with or without permission to various properties that you can never hope to compete with the volume of traffic they enjoy which helps but them above you in the search engine game.
3. Making sure that the web address is on all business correspondence [cards, fax headers/covering sheets, letterheads, small ads in magazines or newspapers] is still one of the best ways of getting known.
If I knew of a sure fire way of getting high search rankings on a regular basis I'd be a very, very rich man.
One hotel I've worked for over the last few years has an unusual name, is situated in a small village and has been designed with search engine optimisation in mind and regularly submitted to all the major engines. I was pleased that it ranked second in a Google search, but it was topped and bottomed by a whole load of hotel indexing sites that offer a "places to stay" type of service.
As long as there are thousands of places to stay in the region you are operating in and sites that offer search facilities of them, those sites will always rank higher than yours.