I am pretty sure this is some problem with the Apache configuration because it used to work on the previous hosting provider with the same PHP/MySQL configuration. In my application, users are able to delete photos by going to URIs like this:

http://example.com/my-account/remove-media/id/9/ret/my-account%252Fedit-album%252Fid%252F1

The paramater id is an id of a photo to be removed, the parameter ret is a relative URL where user should be redirected after the removal of the photo but after clicking on a link like that I get 404 Not Found error with the text:

Not Found

The requested URL /public/my-account/remove-media/id/9/ret/my-account/edit-album/id/1 was not found on this server.

Though it used to work on my previous hosting provider so I guess it is just some easy Apache configuration issue?

One more thing, there is a htaccess file that changes the document root to /public:

RewriteEngine On

php_value upload_max_filesize 15M
php_value post_max_size 15M
php_value max_execution_time 200
php_value max_input_time 200
# Exclude some directories from URI rewriting
#RewriteRule ^(dir1|dir2|dir3) - [L]

RewriteRule ^\.htaccess$ - [F]

RewriteCond %{REQUEST_URI} =""
RewriteRule ^.*$ /public/index.php [NC,L]

RewriteCond %{REQUEST_URI} !^/public/.*$
RewriteRule ^(.*)$ /public/$1

RewriteCond %{REQUEST_FILENAME} -f
RewriteRule ^.*$ - [NC,L]

RewriteRule ^public/.*$ /public/index.php [NC,L]

In the public folder there is a second htaccess file for MVC:

RewriteEngine On
RewriteCond %{REQUEST_FILENAME} -s [OR]
RewriteCond %{REQUEST_FILENAME} -l [OR]
RewriteCond %{REQUEST_FILENAME} -d
RewriteRule ^.*$ - [NC,L]
RewriteRule ^.*$ /index.php [NC,L]

# Turn off magic quotes
#php_flag magic_quotes_gpc off