Which history can't you remove?

For the location bar history see:

• https://support.mozilla.com/kb/Clearing+Location+bar+history
• https://support.mozilla.com/kb/Cannot+clear+Location+bar+history

Entries in the location bar drop down list with a yellow (blue on Mac) star at the right end are bookmarks.
You can remove such a bookmarked item that shows in the list if you open that url in a tab and click the yellow star in the location bar.
This will open the "Edit This Bookmark" dialog and you can click the Remove button to remove the bookmark if you want to remove such a bookmarked entry.

No these dont do the trick - basically, something is badly wrong - I cannot install Java properly, it refuses to run. Also Firefox even though I have deleted my history, it still shows website address in the toolbar that I have tried to delete!

A possible cause is a problem with the file places.sqlite that stores the bookmarks and the history.

• http://kb.mozillazine.org/Bookmarks_history_and_toolbar_buttons_not_working_-_Firefox