Permalinks to Custom does not work (out of box)

I have tried to change mode of .htaccess in wordpress folder to 644. Yet, I get

Not Found
The requested URL /wordpress/features/ was not found on this server.

I keep reading about rearranging my .htaccess to get Permalinks working. Unable to understand.

Here are the details of my .htaccess

# Comment
DirectoryIndex index.html index.htm index.php
<IfModule mod_rewrite.c>
        RewriteEngine On
        RewriteBase /wordpress/
        RewriteCond %{QUERY_STRING} (^|\?|&)s2member_file_download\=.+
        RewriteRule .* - [E=no-gzip:1]
</IfModule>
# BEGIN FlexiCache Standalone
<IfModule mod_rewrite.c>
    RewriteEngine On
    RewriteBase /
    RewriteCond %{HTTP_HOST}        localhost$
    RewriteCond %{REQUEST_METHOD}   GET
    RewriteCond %{REQUEST_URI}      !^/wp-
    RewriteCond %{HTTP_COOKIE}      !(wordpress_logged_in|comment_author|wp-postpass)
    RewriteCond %{REQUEST_FILENAME} !-f
    RewriteCond %{REQUEST_FILENAME} !-d [OR]
    RewriteCond %{REQUEST_URI}      ^/$
    RewriteRule ^(.*)               wp-content/plugins/flexicache/standalone.php [L]
</IfModule>
# END FlexiCache Standalone
# BEGIN W3TC Browser Cache
<IfModule mod_deflate.c>
    <IfModule mod_setenvif.c>
        BrowserMatch ^Mozilla/4 gzip-only-text/html
        BrowserMatch ^Mozilla/4\.0[678] no-gzip
        BrowserMatch \bMSIE !no-gzip !gzip-only-text/html
        BrowserMatch \bMSI[E] !no-gzip !gzip-only-text/html
    </IfModule>
    <IfModule mod_headers.c>
        Header append Vary User-Agent env=!dont-vary
    </IfModule>
    <IfModule mod_filter.c>
        AddOutputFilterByType DEFLATE text/css application/x-javascript text/x-component text/html text/richtext image/svg+xml text/plain text/xsd text/xsl text/xml image/x-icon
    </IfModule>
</IfModule>
<FilesMatch "\.(css|js|htc|CSS|JS|HTC)$">
    <IfModule mod_headers.c>
        Header set Pragma "public"
        Header set Cache-Control "max-age=31536000, public, must-revalidate, proxy-revalidate"
    </IfModule>
    FileETag None
    <IfModule mod_headers.c>
         Header set X-Powered-By "W3 Total Cache/0.9.2.4"
    </IfModule>
</FilesMatch>
<FilesMatch "\.(html|htm|rtf|rtx|svg|svgz|txt|xsd|xsl|xml|HTML|HTM|RTF|RTX|SVG|SVGZ|TXT|XSD|XSL|XML)$">
    <IfModule mod_headers.c>
        Header set Pragma "public"
        Header set Cache-Control "max-age=3600, public, must-revalidate, proxy-revalidate"
    </IfModule>
    FileETag None
    <IfModule mod_headers.c>
         Header set X-Powered-By "W3 Total Cache/0.9.2.4"
    </IfModule>
</FilesMatch>
<FilesMatch "\.(asf|asx|wax|wmv|wmx|avi|bmp|class|divx|doc|docx|eot|exe|gif|gz|gzip|ico|jpg|jpeg|jpe|mdb|mid|midi|mov|qt|mp3|m4a|mp4|m4v|mpeg|mpg|mpe|mpp|otf|odb|odc|odf|odg|odp|ods|odt|ogg|pdf|png|pot|pps|ppt|pptx|ra|ram|svg|svgz|swf|tar|tif|tiff|ttf|ttc|wav|wma|wri|xla|xls|xlsx|xlt|xlw|zip|ASF|ASX|WAX|WMV|WMX|AVI|BMP|CLASS|DIVX|DOC|DOCX|EOT|EXE|GIF|GZ|GZIP|ICO|JPG|JPEG|JPE|MDB|MID|MIDI|MOV|QT|MP3|M4A|MP4|M4V|MPEG|MPG|MPE|MPP|OTF|ODB|ODC|ODF|ODG|ODP|ODS|ODT|OGG|PDF|PNG|POT|PPS|PPT|PPTX|RA|RAM|SVG|SVGZ|SWF|TAR|TIF|TIFF|TTF|TTC|WAV|WMA|WRI|XLA|XLS|XLSX|XLT|XLW|ZIP)$">
    <IfModule mod_headers.c>
        Header set Pragma "public"
        Header set Cache-Control "max-age=31536000, public, must-revalidate, proxy-revalidate"
    </IfModule>
    FileETag None
    <IfModule mod_headers.c>
         Header set X-Powered-By "W3 Total Cache/0.9.2.4"
    </IfModule>
</FilesMatch>
# END W3TC Browser Cache

# BEGIN s2Member GZIP exclusions
<IfModule mod_rewrite.c>
    RewriteEngine On
    RewriteBase /wordpress/
    RewriteCond %{QUERY_STRING} (^|\?|&)s2member_file_download\=.+
    RewriteRule .* - [E=no-gzip:1]
</IfModule>
# END s2Member GZIP exclusions

# BEGIN WordPress
<IfModule mod_rewrite.c>
RewriteEngine On
RewriteBase /wordpress/
RewriteRule ^index\.php$ - [L]
RewriteCond %{REQUEST_FILENAME} !-f
RewriteCond %{REQUEST_FILENAME} !-d
RewriteRule . /wordpress/index.php [L]
</IfModule>

# END WordPress
# BEGIN Security advice from http://www.problogdesign.com/wordpress/11-best-ways-to-improve-wordpress-security/
# 8 – No Directories Should be Available for Browsing
# By default in most hosting, index of directories are shown in web browsers. This has a purpose but it also means that you reveal the content of any directory that has no index.html or index.php.

# Modifying this behavior is easy with Apache, just add the following line of code to the .htaccess file in the root directory (In the same place as the wp-config.php file).
Options All -Indexes
# END Security advice

Edit :
Deactivated all plugins, did the sudo a2enmod rewrite and sudo /etc/init.d/apache2 restart. Enabled permalinks, refreshed the page. The .htaccess file was created automatically. Home page shows up ok (as always), none of the other pages/links work. I tried it on my localhost. My website is hosted on www.mcruiseon.com

# BEGIN WordPress
<IfModule mod_rewrite.c>
RewriteEngine On
RewriteBase /wordpress/
RewriteRule ^index\.php$ - [L]
RewriteCond %{REQUEST_FILENAME} !-f
RewriteCond %{REQUEST_FILENAME} !-d
RewriteRule . /wordpress/index.php [L]
</IfModule>
# END WordPress

Sounds like to that the Allow Override directive is still set to NONE for your VHOST

By default this is disabled, so even if you enable mod_rewrite via sudo a2enmod rewrite your .htaccess will be ignored.

You’ll want to login to your server (via Terminal / shell) and then …

sudo nano /etc/apache2/sites-available/default

look through the file for:

<Directory /var/www/>
    AllowOverride None
    Options MultiViews FollowSymlinks
    Order allow,deny
    Allow from all
    Header Set Cache-Control no-cache
</Directory>

Change the AllowOverride to ALL

Ctrl+x and save the file

then

sudo apache restart or sudo /etc/init.d/apache2 restart

see also http://drupal.org/node/134439

Let me know if the Allow Override was off please?